Submission #114160

#TimeUsernameProblemLanguageResultExecution timeMemory
114160Mamnoon_SiamMinerals (JOI19_minerals)C++17
100 / 100
406 ms4980 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #include "minerals.h" #include <bits/stdc++.h> using namespace std; const int maxn = 43000 + 5; int dp[maxn], opt[maxn]; void solve(vector<int> u, vector<int> v, int f) { if(u.size() == 1) { Answer(u.back(), v.back()); return; } int mid, last; if(f) { mid = u.size() - opt[u.size()]; for(int i = mid; i < v.size(); i++) { last = Query(v[i]); } } else { mid = opt[u.size()]; for(int i = 0; i < mid; i++) { last = Query(v[i]); } } vector<int> lu, lv(v.begin(), v.begin() + mid); vector<int> 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]); // < This part reduces Query() } else if(ru.size() == rv.size()) { // < call by at least N - 1 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) { vector<int> l, r; int last = -1; for(int i = 0; i < v.size(); i++) { if(r.size() == v.size() / 2) { // < This part reduces Query() l.emplace_back(v[i]); // < call by at least 1 } else { 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) { dp[1] = 0; for(int i = 2; i <= N; i++) { int mn = INT_MAX, tmp, arg; const int cmp = (i - 1) / 2 + 1; for(int j = 1; j <= cmp; j++) { tmp = dp[j] + dp[i - j] + (j < cmp ? j : i - j); if(tmp < mn) { mn = tmp; arg = j; } } dp[i] = mn + i - 1; opt[i] = arg; } /* In worst case scenario, maximum number of calls to Query() is dp[N] + 2N - 1. */ 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:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = mid; i < v.size(); i++) {
                    ~~^~~~~~~~~~
minerals.cpp:31: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:54: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:38:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(rep == last) {
    ^~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:82:10: warning: 'arg' may be used uninitialized in this function [-Wmaybe-uninitialized]
   opt[i] = arg;
   ~~~~~~~^~~~~
#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...