제출 #605177

#제출 시각아이디문제언어결과실행 시간메모리
605177Sam_a17버섯 세기 (IOI20_mushrooms)C++14
92.62 / 100
140 ms1556 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define dbg(x) cout << #x << " " << x << endl; #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define pb push_back #define ld long double #define ll long long // #include "mushrooms.h" int use_machine(vector<int> m); void pr(vector<int>& a) { cerr << "arr" << " "; for(auto i: a) { cerr << i << " "; } cerr << endl; } // #include "mushrooms.h" int use_machine(vector<int> m); int count_mushrooms(int n) { set<int> st; for(int i = 0; i < n; i++) { st.insert(i); } int answ = 0; int kAx = 1, kBx = 0, cnt = 0, qn = 0; int lim = 80; vector<int> ones, zeroes{0}; int start = -1; for(int i = 1; i < n; i++) { vector<int> aski{0, i}; int s = use_machine(aski); if(s == 1) { ones.push_back(i); kBx++; } else { zeroes.push_back(i); kAx++; } if(kAx >= 2 || kBx >= 2) { start = i + 1; break; } } if(start == -1) { return kAx; } if(kAx >= 2) { for(int i = start; i + 1 < n; i += 2) { vector<int> ask{0, i, zeroes.back(), i + 1}; int s = use_machine(ask); if(s == 0) { zeroes.push_back(i); zeroes.push_back(i + 1); } else if(s == 1) { zeroes.push_back(i); ones.push_back(i + 1); } else if(s == 2) { ones.push_back(i); zeroes.push_back(i + 1); } else { ones.push_back(i); ones.push_back(i + 1); } // kAx = sz(zeroes), kBx = sz(ones); if(kAx >= lim || kBx >= lim) { start = i + 2; break; } start += 2; } } else { for(int i = start; i + 1 < n; i += 2) { vector<int> ask{ones.front(), i, ones.back(), i + 1}; int s = use_machine(ask); if(s == 0) { ones.push_back(i); ones.push_back(i + 1); } else if(s == 1) { ones.push_back(i); zeroes.push_back(i + 1); } else if(s == 2) { zeroes.push_back(i); ones.push_back(i + 1); } else { zeroes.push_back(i); zeroes.push_back(i + 1); } // kAx = sz(zeroes), kBx = sz(ones); if(kAx >= lim || kBx >= lim) { start = i + 2; break; } start += 2; } } // pr(zeroes); // pr(ones); // dbg(answ) int countt = 0; while(start < n) { kAx = sz(zeroes), kBx = sz(ones); // dbg(kAx) // dbg(kBx) if(kAx > kBx) { vector<int> qry; for(int j = start, k = 0; j < min(n, start + kAx); j++, k++) { qry.push_back(zeroes[k]); qry.push_back(j); } if(!qry.empty()) { int s = use_machine(qry); int ci = 0; bool flag = false; if(s % 2 == 1) { s--, ci++; ones.push_back(qry.back()); } else { countt++; zeroes.push_back(qry.back()); } answ += (sz(qry) / 2 - ci) - (s / 2); } } else { vector<int> qry; for(int j = start, k = 0; j < min(n, start + kBx); j++, k++) { qry.push_back(ones[k]); qry.push_back(j); } if(!qry.empty()) { int s = use_machine(qry); pr(qry); int ci = 0; if(s % 2 == 1) { s++, countt++; zeroes.push_back(qry.back()); } else { ones.push_back(qry.back()); } // dbg(s) answ += (s / 2); } } start += max(kAx, kBx); } return answ + sz(zeroes) - countt; }

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:142:14: warning: unused variable 'flag' [-Wunused-variable]
  142 |         bool flag = false;
      |              ^~~~
mushrooms.cpp:163:13: warning: unused variable 'ci' [-Wunused-variable]
  163 |         int ci = 0;
      |             ^~
mushrooms.cpp:36:25: warning: unused variable 'cnt' [-Wunused-variable]
   36 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                         ^~~
mushrooms.cpp:36:34: warning: unused variable 'qn' [-Wunused-variable]
   36 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...