제출 #640840

#제출 시각아이디문제언어결과실행 시간메모리
640840blue드문 곤충 (IOI22_insects)C++17
0 / 100
1 ms208 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #define sz(x) int(x.size()) const int mx = 2'000; vi ins(mx, 0); int ct = 0; vi dp(mx + 5, 0); vi opt(mx + 5, 0); int getRandom(int l, int r) { return rand() % (r-l+1); } void move_in(int i) { // cerr << "insert " << i << '\n'; if(ins[i]) return; ins[i] = 1; move_inside(i); ct++; } void move_out(int i) { // cerr << "erase " << i << '\n'; if(!ins[i]) return; ins[i] = 0; move_outside(i); ct--; } int Z = 0; //number of species void solve(vi lst, int b) //b = basic value { if(sz(lst) < Z) return; int mx = sz(lst)/Z; int I = sz(lst); int med = opt[sz(lst)]; vi ins, notins; int to_exc = -1; bool flag = 0; for(int i : lst) { if(ct == (med + b) * Z) { notins.push_back(i); continue; } move_in(i); int pb = press_button(); if(pb - b > med) { move_out(i); notins.push_back(i); } else { if(pb - b == med && flag == 0) { to_exc = i; flag = 1; } ins.push_back(i); } } if(ct == (med + b) * Z) { solve(notins, b + med); } else { for(int i : ins) move_out(i); vi new_ins; for(int i : ins) if(i != to_exc) new_ins.push_back(i); solve(new_ins, b); } } int min_cardinality(int N) { vi lst; for(int i = 0; i < N; i++) { move_in(i); if(press_button() >= 2) { move_out(i); lst.push_back(i); } else Z++; } for(int i = 0; i <= N; i++) { dp[i] = 5'000'000; opt[i] = -1; if(i < Z) { dp[i] = 0; } else { for(int j = 1; j <= i/Z; j++) { int cand = i + max(dp[i - j*Z], dp[j*Z]); if(cand < dp[i]) { dp[i] = cand; opt[i] = j; } // dp[i] = min(dp[i], i + max(dp[i - j*Z], dp[j*Z])); } } } solve(lst, 1); return ct / Z; }

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

insects.cpp: In function 'void solve(vi, int)':
insects.cpp:51:6: warning: unused variable 'mx' [-Wunused-variable]
   51 |  int mx = sz(lst)/Z;
      |      ^~
insects.cpp:53:6: warning: unused variable 'I' [-Wunused-variable]
   53 |  int I = sz(lst);
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...