Submission #315434

#TimeUsernameProblemLanguageResultExecution timeMemory
315434VROOM_VARUNDancing Elephants (IOI11_elephants)C++14
26 / 100
9021 ms3548 KiB
/* ID: varunra2 LANG: C++ TASK: elephants */ // cp ~/SNIPPETS/Template/testing/* // gen.cpp and build with IORun // create brute.cpp and build with IORun // this runs 5 random tests against a with checkts against brute // ./test.sh 5 a // any failed tests will be saved under data/failed*{inp,out,oac} pattern. .oac // is output of brute, .out is output of program, .inp is output of gen #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions int n, l; const int BLOCK = 3; multiset<PII> st; VI vals; struct block { VI pnts; int siz; VI dp1; // how many blocks for suffix starting at i, ending at pnts.size()? VI dp2; // where does the optimal solution held at dp1[i] end? void init() { sort(all(pnts)); siz = sz(pnts); dp1.resize(siz); dp2.resize(siz); } void calc() { init(); int p1 = siz - 1; for (int i = siz - 1; i >= 0; i--) { while ((pnts[p1] - pnts[i]) > l) p1--; if (p1 == siz - 1) { dp1[i] = 1; dp2[i] = pnts[i] + l; } else { dp1[i] = dp1[p1 + 1] + 1; dp2[i] = dp2[p1 + 1]; } } } void ins(int x) { pnts.PB(x); calc(); } void del(int x) { VI cop; trav(xx, pnts) { if (xx == x) continue; cop.PB(xx); } pnts = cop; calc(); } PII get(int x) { // how many to cover rest of this block starting at x // where would it end at auto it = upper_bound(all(pnts), x); if (it == pnts.end()) { return MP(0, x); } int ind = it - pnts.begin(); return MP(dp1[ind], dp2[ind]); } void pr(int i = -1) { debug("printing block", i); debug("pnts", pnts); debug("dp1", dp1); debug("dp2", dp2); } }; vector<block> blocks; void rebuild(bool done = true) { // we are rebuilding blocks VI pnts; pnts = vals; blocks.clear(); sort(all(pnts)); VI cur; st.clear(); for (int i = 0; i < sz(pnts); i++) { cur.PB(pnts[i]); st.insert(MP(pnts[i], sz(blocks))); if (sz(cur) == BLOCK) { block nw; nw.pnts = cur; nw.calc(); cur.clear(); blocks.PB(nw); } } if (!cur.empty()) { block nw; nw.pnts = cur; nw.calc(); cur.clear(); blocks.PB(nw); } } void ins(int x) { debug("we got an insertation - reeeeeeeeeeeeeeeeeee"); debug(x); // what block are we in? auto it = st.lower_bound(MP(x, -1)); if(it == st.end()) { int ind = sz(blocks) - 1; blocks[ind].ins(x); st.insert(MP(x, ind)); return; } auto xx = *it; blocks[xx.y].ins(x); st.insert(MP(x, xx.y)); debug(st); debug(xx); } void del(int x) { debug("we got a deletion - wooooooooooooooooooooooo"); debug(x); auto xx = *st.lower_bound(MP(x, -1)); blocks[xx.y].del(x); st.erase(st.lower_bound(MP(x, -1))); debug(st); } int qry() { debug("we got a query - uh oh"); int ret = 0; int ind = -1; for (int i = 0; i < sz(blocks); i++) { auto x = blocks[i].get(ind); ret += x.x; ind = x.y; debug(ret, ind); } return ret; } void init(int N, int L, int X[]) { n = N; l = L; for (int i = 0; i < n; i++) { vals.PB(X[i]); } rebuild(false); // first time building } int cnt = 0; int update(int i, int y) { debug("we got an update asdfasfsdfasfasdfasfsadfasdfa"); int cur = vals[i]; vals[i] = y; debug(vals); del(cur); ins(y); cnt++; if (cnt % BLOCK == 0) { rebuild(); } return qry(); } // int main() { // #ifndef ONLINE_JUDGE // freopen("elephants.in", "r", stdin); // freopen("elephants.out", "w", stdout); // #endif // cin.sync_with_stdio(0); // cin.tie(0); // string barrier = // "======================================================================="; // debug(barrier); // int n, l, q; // cin >> n >> l >> q; // int x[n]; // for (int i = 0; i < n; i++) { // cin >> x[i]; // } // init(n, l, x); // debug(qry()); // while (q--) { // int i, y; // cin >> i >> y; // debug(i, y); // int correct; // cin >> correct; // int ret = update(i, y); // debug(ret); // debug(correct); // debug(ret == correct); // assert(ret == correct); // } // return 0; // }

Compilation message (stderr)

elephants.cpp: In member function 'void block::pr(int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:124:5: note: in expansion of macro 'debug'
  124 |     debug("printing block", i);
      |     ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:125:5: note: in expansion of macro 'debug'
  125 |     debug("pnts", pnts);
      |     ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:126:5: note: in expansion of macro 'debug'
  126 |     debug("dp1", dp1);
      |     ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:127:5: note: in expansion of macro 'debug'
  127 |     debug("dp2", dp2);
      |     ^~~~~
elephants.cpp: In function 'void ins(int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:166:3: note: in expansion of macro 'debug'
  166 |   debug("we got an insertation - reeeeeeeeeeeeeeeeeee");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:167:3: note: in expansion of macro 'debug'
  167 |   debug(x);
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:179:3: note: in expansion of macro 'debug'
  179 |   debug(st);
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:180:3: note: in expansion of macro 'debug'
  180 |   debug(xx);
      |   ^~~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:184:3: note: in expansion of macro 'debug'
  184 |   debug("we got a deletion - wooooooooooooooooooooooo");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:185:3: note: in expansion of macro 'debug'
  185 |   debug(x);
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:189:3: note: in expansion of macro 'debug'
  189 |   debug(st);
      |   ^~~~~
elephants.cpp: In function 'int qry()':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:193:3: note: in expansion of macro 'debug'
  193 |   debug("we got a query - uh oh");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:200:5: note: in expansion of macro 'debug'
  200 |     debug(ret, ind);
      |     ^~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:217:3: note: in expansion of macro 'debug'
  217 |   debug("we got an update asdfasfsdfasfasdfasfsadfasdfa");
      |   ^~~~~
elephants.cpp:26:20: warning: statement has no effect [-Wunused-value]
   26 | #define debug(...) 42
      |                    ^~
elephants.cpp:220:3: note: in expansion of macro 'debug'
  220 |   debug(vals);
      |   ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...