Submission #112234

#TimeUsernameProblemLanguageResultExecution timeMemory
112234AngusRitossaMinerals (JOI19_minerals)C++14
90 / 100
95 ms3100 KiB
#include "minerals.h" #include <bits/stdc++.h> #include <chrono> #include <random> #ifdef DEBUG #define D(x...) printf(x) #else #define D(x...) #endif using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, pre; vector<int> before, after; int other[2*70000]; int c; int doQuery(int a) { c++; assert(c != 1.1e6); D("querying %d\n", a); return Query(a); } void solve(vector<int> &b, vector<int> &a, bool inv = 0, bool shouldrem = 1, int half = -1) { D("\n%lu %lu inv %d\n", a.size(), b.size(), inv); for (auto i : b) D("%d ", i); D(" a\n"); for (auto i : a) D("%d ", i); D(" b\n"); assert(a.size() == b.size()); if (b.size() == 1) { other[a[0]] = b[0]; return; } vector<int> firsthalf, secondhalf; vector<int> fa, sa; int ignore = -1; if (half == -2) ignore = b.size()-1; if (half < 0) { half = b.size()/2; if (shouldrem) half += b.size()/10; } for (int i = 0; i < b.size(); i++) { if (i < half) firsthalf.push_back(b[i]), assert(i != ignore); else { secondhalf.push_back(b[i]); if (shouldrem && i != ignore) pre = doQuery(b[i]); else if (shouldrem) D("ignored %d\n", b[i]); } } if (inv) swap(firsthalf, secondhalf); int oldpre = pre; int sta = 0; shuffle(a.begin(), a.end(), rng); for (auto i : a) { if (fa.size() == b.size()-1) { sa.push_back(i); continue; } if (sa.size() == b.size()-1) { fa.push_back(i); continue; } if (fa.size() == firsthalf.size() && pre < oldpre) { sa.insert(sa.begin(), i); sta++; continue; } else if (sa.size() == secondhalf.size() && fa.size()+1 == firsthalf.size()) { sta--; fa.push_back(i); // D("doing this! %d\n", i); continue; } int q = doQuery(i); if (q == pre) { fa.push_back(i); } else { sa.push_back(i); } pre = q; } int h = -1; if (sta == -1) h = -2; if (h != -2) solve(firsthalf, fa, 0, 1, h); else solve(fa, firsthalf, pre < oldpre, 1, h); if (pre >= oldpre) { solve(sa, secondhalf, 0); } else { sta = max(sta, 0); int half = sa.size()/2; half -= sa.size()/10; if (sta-1 >= half) half += sa.size()/10; while (sta-1 >= half) { pre = doQuery(sa[--sta]); } for (int i = sta; i < half; i++) pre = doQuery(sa[i]); solve(sa, secondhalf, 0, 0, half); } } void Solve(int N) { n = N; for (int i = 1; i <= 2*n; i++) { int q = doQuery(i); if (q != pre) before.push_back(i); else after.push_back(i); pre = q; } solve(before, after); for (int i = 1; i <= 2*n; i++) { if (other[i]) { Answer(i, other[i]); } } }

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool, bool, int)':
minerals.cpp:27:12: warning: unused variable 'i' [-Wunused-variable]
  for (auto i : b) D("%d ", i);
            ^
minerals.cpp:29:12: warning: unused variable 'i' [-Wunused-variable]
  for (auto i : a) D("%d ", i);
            ^
minerals.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...