Submission #972220

#TimeUsernameProblemLanguageResultExecution timeMemory
972220RaresFelixThe Potion of Great Power (CEOI20_potion)C++17
38 / 100
3052 ms236928 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") using namespace std; using ii = pair<int, int>; using vi = vector<int>; int n, rad; int *H0, *A0, *B0; vi Perm, Inv; vector<vi> Snapshot; vector<vi> Mare; vector<vi> S; void init(int N, int D, int H[]) { n = N; H0 = H; S.resize(n); Inv.resize(n); for(int i = 0; i < n; ++i) Perm.push_back(i); sort(Perm.begin(), Perm.end(), [&](auto a, auto b) { return H[a] < H[b]; }); for(int i = 0; i < n; ++i) Inv[Perm[i]] = i; } void curseChanges(int U, int A[], int B[]) { rad = min(U, 500); A0 = A; B0 = B; auto erase = [&](vi &V, int val) { vi Re; for(auto &it : V) if(it != val) Re.push_back(it); return Re; }; vector<int> changed(n, 1); for(int nr = 0; nr < U; ++nr) { A[nr] = Inv[A[nr]]; B[nr] = Inv[B[nr]]; } for(int nr = 0; nr < U; ++nr) { if(nr % rad == 0) { vi cur; for(int i = 0; i < n; ++i) { if(changed[i]) { cur.push_back(Mare.size()); Mare.push_back(S[i]); changed[i] = 0; } else { cur.push_back(Snapshot.back()[i]); } } Snapshot.push_back(cur); } int a = A[nr], b = B[nr]; int ok = 0; for(auto it : S[a]) if(it == b) ok = 1; changed[a] = 1; changed[b] = 1; if(ok) { S[a] = erase(S[a], b); S[b] = erase(S[b], a); } else { S[b].push_back(a); S[a].push_back(b); } } } const int INF = 1e9; int question(int x, int y, int v) { if(!v) { return INF; } --v; x = Inv[x]; y = Inv[y]; vi VSX = Mare[Snapshot[v / rad][x]]; vi VSY = Mare[Snapshot[v / rad][y]]; set<int> SX, SY; for(auto it : VSX) SX.insert(it); for(auto it : VSY) SY.insert(it); for(int i = v / rad * rad; i <= v; ++i) { int a = A0[i], b = B0[i]; if(b == x) swap(a, b); if(a == x) { if(SX.count(b)) SX.erase(b); else SX.insert(b); } if(b == y) swap(a, b); if(a == y) { if(SY.count(b)) SY.erase(b); else SY.insert(b); } } vi VA, VB; for(auto it : SX) VA.push_back(H0[Perm[it]]); for(auto it : SY) VB.push_back(H0[Perm[it]]); // for(auto it : VA) cerr << it << " "; // cerr << "\n"; // for(auto it : VB) cerr << it << " "; // cerr << "\n"; // cerr << "\n"; int p1 = 0, p2 = 0; int re = INF; while(p1 < VA.size() && p2 < VB.size()) { re = min(re, abs(VB[p2] - VA[p1])); if(VA[p1] < VB[p2]) ++p1; else ++p2; } return re; }

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:122:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     while(p1 < VA.size() && p2 < VB.size()) {
      |           ~~~^~~~~~~~~~~
potion.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     while(p1 < VA.size() && p2 < VB.size()) {
      |                             ~~~^~~~~~~~~~~
#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...