fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <set>
  5. #include <deque>
  6. #include <algorithm>
  7. #include <queue>
  8. #include <cmath>
  9. #include <map>
  10. #include <complex>
  11. #include <cstring>
  12. #include <cfloat>
  13. #include <iomanip>
  14. #include <stack>
  15. #include <bitset>
  16.  
  17.  
  18. using namespace std;
  19. #define rep(i, a, b) for(int i = (a); i < (b); i++)
  20. #define repd(i, a, b) for(int i = (a); i > (b); i--)
  21. #define forIt(it, a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
  22. #define forRev(it, a) for(__typeof((a).rbegin()) it = (a).rbegin(); it != (a).rend(); it++)
  23. #define ft(a) __typeof((a).begin())
  24. #define ll long long
  25. #define ld long double
  26. #define fi first
  27. #define se second
  28. #define mk make_pair
  29. #define pb push_back
  30. #define sz(a) (int)(a).size()
  31. #define all(a) (a).begin(), (a).end()
  32. #define Rep(i,n) for(int i = 0; i < (n); ++i)
  33. #define bitcount(n) __builtin_popcountll(n)
  34. #define pii pair<int, int>
  35.  
  36.  
  37. typedef complex<ld> cplex;
  38. typedef vector<int> vi;
  39. typedef pair<int, int> ii;
  40. typedef pair<ii, int> iii;
  41. typedef vector<ii> vii;
  42. typedef vector<iii> viii;
  43.  
  44. const int N = 200000 + 7;
  45. const int M = 1000 + 3;
  46. const int inf = 1e9 + 7;
  47. const long long linf = 1ll * inf * (inf - 1);
  48. const double pi = acos(-1);
  49. const double eps = 1e-6;
  50. const bool multipleTest = false;
  51.  
  52.  
  53. int c, n;
  54. int st[N];
  55.  
  56. int prv[N];
  57. vii list;
  58.  
  59. void solve() {
  60.     cin >> c >> n;
  61.     for(int i = 1; i <= n; ++i) {
  62.         int u; scanf("%d", &u);
  63.         st[u]++;
  64.     }
  65.  
  66.     for(int i = 1; i <= c; ++i) if (st[i])
  67.         list.push_back(mk(i, st[i]));
  68.     int p = 0;
  69.  
  70.     for(int cur = 1; cur <= c; ++cur) {
  71.         prv[cur] = -1;
  72.  
  73.         while (p + 1 < list.size() && list[p + 1].first <= cur) ++p;
  74.         if (list[p].first <= cur) prv[cur] = p;
  75. //        cout << cur << " ";
  76. //        if (prv[cur] != -1) {
  77. //            cout << list[prv[cur]].first << " " << list[prv[cur]].second;
  78. //        }
  79. //        puts("");
  80.     }
  81.  
  82.  
  83.  
  84.  
  85.     for(int d = 1; d <= c; ++d) {
  86.  
  87.         bool used = false;
  88.  
  89.         int cur = c;
  90.         int cs = list.size();
  91.         while (cur > 0) {
  92.  
  93.             int u = min(prv[cur], cs - 1);
  94.             if (u == -1 && used) break;
  95.  
  96.             if (u == -1 || (!used && d >= list[u].first)) {
  97.                 used = true;
  98.                 if (cur >= d) cur -= d;
  99.                 continue;
  100.             }
  101.  
  102.             int gt = list[u].first, sl = list[u].second;
  103.             cs = u;
  104.  
  105.             sl = min(sl, cur / gt);
  106.             cur -= sl * gt;
  107.  
  108.         }
  109. //        cout << d << " " << cur << "\n";
  110.         if (cur > 0) {
  111.             cout << d << "\n";
  112.             return;
  113.         }
  114.     }
  115.  
  116.  
  117.  
  118.  
  119.     puts("Greed is good");
  120.  
  121.  
  122.  
  123.  
  124.  
  125. }
  126.  
  127. void createTest() {
  128.     freopen("in.txt", "w", stdout);
  129.     cout << 1 << "\n";
  130.     cout << 100000 << " " << 100000 << "\n";
  131.     for(int i = 1; i <= 100000; ++i) {
  132.         int u = rand();
  133.         int v = rand();
  134.         if (u > v) swap(u, v); printf("%d %d\n", u, v);
  135.     }
  136.     for(int i = 1; i <= 100000; ++i) {
  137.         int u = rand();
  138.         int v = rand();
  139.         if (u > v) swap(u, v); printf("%d %d\n", u, v);
  140.     }
  141. }
  142.  
  143.  
  144.  
  145. int main() {
  146. #ifndef ONLINE_JUDGE
  147.     freopen("in.txt", "r", stdin);
  148.     clock_t t1 = clock();
  149. #endif
  150.     //            createTest();
  151.     //            return 0;
  152.     //        freopen("out.txt", "w", stdout);
  153.  
  154.  
  155.  
  156.  
  157.     int Test = 1;
  158.     if (multipleTest) {
  159.         cin >> Test;
  160.     }
  161.  
  162.     for(int i = 0; i < Test; ++i) {
  163.         //                printf("Case #%d: ", i + 1);
  164.         solve();
  165.     }
  166.     //
  167. #ifndef ONLINE_JUDGE
  168.     cout<<"\n" << 1.0 * (clock() - t1) / CLOCKS_PER_SEC<<endl;
  169. #endif
  170.  
  171. }
Success #stdin #stdout 0s 5036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Greed is good
https://ideone.com/56lb0F
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!