Submission #113877

#TimeUsernameProblemLanguageResultExecution timeMemory
113877Mamnoon_SiamMinerals (JOI19_minerals)C++17
90 / 100
77 ms4144 KiB
#include "minerals.h" #include <bits/stdc++.h> using namespace std; mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x; } struct RNG { int operator () (int n) { return rnd(n); } }; void solve(vector<int> u, vector<int> v, int f) { if(u.empty()) return; if(u.size() == 1) { Answer(u.back(), v.back()); return; } random_shuffle(u.begin(), u.end(), RNG()); int mid = u.size() >> 1; int last; if(f) { for(int i = mid; i < v.size(); i++) { last = Query(v[i]); } } else { for(int i = 0; i < mid; i++) { last = Query(v[i]); } } vector<int> lu, lv(v.begin(), v.begin() + mid), ru, rv(v.begin() + mid, v.end()); for(int i = 0; i < u.size(); i++) { if(lu.size() == lv.size()) { ru.emplace_back(u[i]); } else if(ru.size() == rv.size()) { lu.emplace_back(u[i]); } else { int rep = Query(u[i]); if(rep == last) { lu.emplace_back(u[i]); } else { ru.emplace_back(u[i]); } last = rep; } } solve(lu, lv, 1); solve(ru, rv, 0); } void split(vector<int> v) { if(v.size() == 2) return Answer(v[0], v[1]); vector<int> l, r; int last = -1; for(int i = 0; i < v.size(); i++) { if(r.size() == v.size() / 2) { l.emplace_back(v[i]); continue; } int rep = Query(v[i]); if(rep == last) { l.emplace_back(v[i]); } else { r.emplace_back(v[i]); } last = rep; } solve(l, r, 1); } void Solve(int N) { vector<int> v(2 * N); iota(v.begin(), v.end(), 1); split(v); }

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void split(std::vector<int>)':
minerals.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, int)':
minerals.cpp:40:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~
#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...