제출 #897637

#제출 시각아이디문제언어결과실행 시간메모리
897637Essa2006버섯 세기 (IOI20_mushrooms)C++17
25 / 100
30 ms1060 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define FF first #define SS second #define all(a) a.begin(), a.end() #define mod (ll)(1000000007) #include "mushrooms.h" //int cnt = 0; // //vector<int> B; // //int use_machine(vector<int> X) { // cnt++; // int res = 0; // for (int i = 1; i < X.size(); i++) { // if (B[X[i]] != B[X[i - 1]]) { // res++; // } // } // return res; //} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int count_mushrooms(int n) { vector<int> A(n); vector<int> Z = {0}, O; for (int i = 0; i < n; i++) { A[i] = i; } shuffle(A.begin() + 1, A.end(), rng); int ans = 1; int fir, sec; int cur = use_machine({A[0], A[1]}); if (cur) { O.push_back(A[1]); } else{ Z.push_back(A[1]); ans++; } if (n == 2) return ans; int cur2 = use_machine({A[0], A[2]}); if (cur2) { O.push_back(A[2]); } else{ Z.push_back(A[2]); ans++; } int i = 3; while (i < n - 1) { int j = i; vector<int>Ask; if (Z.size() > O.size()) { while (j < n){ Ask.push_back(A[j]); if (Z.size() < j - i + 1 || j == n - 1) { j++; break; } Ask.push_back(Z[j - i]); j++; } int diff = use_machine(Ask); int all = (Ask.size() + 1) / 2; if (diff & 1) { int Bs = (diff + 1) / 2; ans += all - Bs; } else { int diff2 = use_machine({Z.front(), A[i]}); if (diff2) { O.push_back(A[i]); O.push_back(A[j - 1]); ans += all - (diff + 2)/ 2; } else { Z.push_back(A[i]); Z.push_back(A[j - 1]); ans += all - diff / 2; } } } else { while (j < n){ Ask.push_back(A[j]); if (O.size() < j - i + 1 || j == n - 1) { j++; break; } Ask.push_back(O[j - i]); j++; } int diff = use_machine(Ask); int all = (Ask.size() + 1) / 2; if (diff & 1) { int As = (diff + 1) / 2; ans += As; } else { int diff2 = use_machine({O.front(), A[i]}); if (diff2) { Z.push_back(A[i]); Z.push_back(A[j - 1]); ans += (diff / 2 + 1); } else { O.push_back(A[i]); O.push_back(A[j - 1]); ans += diff / 2; } } } i = j; } if (i == n - 1) { int diff = use_machine({Z.front(), A[i]}); ans += 1 - diff; } return ans; } //int main() { // int n, m; // cin >> n >> m; // // int mx = 0; // for (int times = 0; times < m; times++) { // B.clear(); // B.resize(n); // // cnt = 0; // for (int i = 0; i < n; i++) { // B[i] = rng() % 2; // } // // int res = count_mushrooms(n); // mx = max(mx, cnt); // } // cout << mx; //}

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

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:70:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |                 if (Z.size() < j - i + 1 || j == n - 1) {
      |                     ~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |                 if (O.size() < j - i + 1 || j == n - 1) {
      |                     ~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:109:17: warning: unused variable 'all' [-Wunused-variable]
  109 |             int all = (Ask.size() + 1) / 2;
      |                 ^~~
mushrooms.cpp:39:9: warning: unused variable 'fir' [-Wunused-variable]
   39 |     int fir, sec;
      |         ^~~
mushrooms.cpp:39:14: warning: unused variable 'sec' [-Wunused-variable]
   39 |     int fir, sec;
      |              ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...