Submission #1039282

#TimeUsernameProblemLanguageResultExecution timeMemory
1039282TonylThe Potion of Great Power (CEOI20_potion)C++17
17 / 100
278 ms139924 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; #define REP(i,n) for (int i = 0; i < n; i++) #define trav(a,x) for (auto &a : x) #define all(x) (x).begin(), (x).end() #define submit(a,b) cout << a << " " << b << endl #define D(x) //cerr << #x << ": " << x << endl; int n,d; vi alln; struct Treap { int num; int prio; Treap *left = nullptr, *right = nullptr; Treap(Treap *t) { num = t->num; prio = rand(); //t->prio; } Treap(int nm, int pr) { num = nm; prio = rand(); // pr; } Treap(int nm) { num = nm; prio = rand(); } void check_depth(int depth = 0) { assert(depth < 20); if (left != nullptr) left->check_depth(depth+1); if (right != nullptr) right->check_depth(depth+1); } void gather_all() { alln.push_back(num); if (left != nullptr) left->gather_all(); if (right != nullptr) right->gather_all(); } }; Treap* merge(Treap* left, Treap* right) { if (left == nullptr) return right; if (right == nullptr) return left; if (left->prio <= right->prio) { Treap *t = new Treap(left); t->left = left->left; t->right = merge(left->right, right); return t; } else { Treap *t = new Treap(right); t->right = right->right; t->left = merge(left, right->left); return t; } } pair<Treap*, Treap*> split(Treap* tr, int num) { if (tr == nullptr) return {tr, tr}; if (tr->num < num) { Treap *t = new Treap(tr); t->left = tr->left; auto p = split(tr->right, num); t->right = p.first; return {t, p.second}; } else { Treap *t = new Treap(tr); t->right = tr->right; auto p = split(tr->left, num); t->left = p.second; return {p.first, t}; } } const int MAX_N = 1e5+2; Treap* smol[MAX_N]; Treap* flipp(Treap* tr, int num) { Treap *lower, *exact, *bigger; auto p = split(tr, num); lower = p.first; auto p2 = split(p.second, num+1); exact = p2.first; bigger = p2.second; if (exact == nullptr) exact = smol[num]; else exact = nullptr; Treap* t = merge(lower, exact); return merge(t, bigger); } struct TimeTraveller { vector<pair<int, Treap*>> history; TimeTraveller() { history.push_back({-1, nullptr}); } void flip(int i, int time) { Treap* c = flipp(history.back().second, i); if (rand() % 100 == 0) c->check_depth(); history.push_back({time, c}); } void gather_all(int time) { auto p = lower_bound(all(history), pair<int, Treap*>(time+1, nullptr)); p--; alln = vi(); if (p->second == nullptr) return; p->second->gather_all(); assert(alln.size() <= d); } }; vi hs; TimeTraveller fr[MAX_N]; vi aaa, bbb, h1, h2; int get_ans() { int best = 1e9; h1 = vi(); h2 = vi(); trav(aa, aaa) { h1.push_back(hs[aa]); } sort(all(h1)); trav(bb, bbb) { h2.push_back(hs[bb]); } sort(all(h2)); if (h1.size() == 0) return best; int i = 0; trav(hb, h2) { while (h1[i] < hb && i != h1.size()-1) i++; best = min(best, abs(hb - h1[i])); if (i!=0) best = min(best, abs(hb - h1[i-1])); } return best; } bool called = false; void init(int N, int D, int H[]) { srand(899852); n = N; d = D; REP(i,n) hs.push_back(H[i]); REP(i,n) smol[i] = new Treap(i, rand()); } void curseChanges(int U, int A[], int B[]) { assert(!called); called = 1; REP(uu, U) { int a = A[uu]; int b = B[uu]; fr[a].flip(b, uu+1); fr[b].flip(a, uu+1); } } int question(int x, int y, int v) { fr[x].gather_all(v); aaa = alln; fr[y].gather_all(v); bbb = alln; return get_ans(); //return get_ans(fr[x].gather_all(v), fr[y].gather_all(v)); }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from potion.cpp:1:
potion.cpp: In member function 'void TimeTraveller::gather_all(int)':
potion.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |         assert(alln.size() <= d);
      |                ~~~~~~~~~~~~^~~~
potion.cpp: In function 'int get_ans()':
potion.cpp:145:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         while (h1[i] < hb && i != h1.size()-1) i++;
      |                              ~~^~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...