Submission #66852

#TimeUsernameProblemLanguageResultExecution timeMemory
66852BenqKoala Game (APIO17_koala)C++14
100 / 100
83 ms828 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; // #define LOCAL #ifdef LOCAL void playRound(int *B, int *R); #else #include "koala.h" #endif int B[100], R[100]; void clr() { F0R(i,100) B[i] = 0; } int minValue(int N, int W) { clr(); B[0] = 1; playRound(B,R); F0R(i,N) if (R[i] <= B[i]) return i; return -1; } void prin() { F0R(i,100) cout << B[i] << " "; cout << "\n"; F0R(i,100) cout << R[i] << " "; cout << "\n"; } void upd(vi& v) { vi V; for (int i: v) if (R[i] > B[i]) V.pb(i); v = V; } int maxValue(int N, int W) { vi cand; F0R(i,N) cand.pb(i); while (sz(cand) > 1) { clr(); for (int i: cand) B[i] = 100/sz(cand); playRound(B,R); upd(cand); } return cand[0]; } int greaterValue(int N, int W) { int lo = 1, hi = 9; while (1) { int mid = (lo+hi)/2; clr(); B[0] = B[1] = mid; playRound(B,R); if (R[0] > B[0]) { if (R[1] > B[1]) { lo = mid+1; } else { return 0; } } else { if (R[1] > B[1]) { return 1; } else { hi = mid-1; } } } } int cdiv(int x, int y) { return (x+y-1)/y; } void divi(int N, int W, int *P, int mx, vi cand) { if (sz(cand) == 1) { P[cand[0]] = mx; return; } int wei = W/sz(cand); if (W == N) { wei = min(wei,8); if (mx <= 8) wei = 2; if (mx == 2) wei = 1; if (mx == 16 && sz(cand) == 2) wei = 5; if ((mx == 18 || mx == 19) && sz(cand) <= 3) wei = 6; if (mx == 21 && sz(cand) == 2) wei = 6; if (mx == 25 && sz(cand) == 2) wei = 7; } clr(); for (int i: cand) B[i] = wei; playRound(B,R); vi a,b; for (int i: cand) { if (R[i] <= B[i]) a.pb(i); else b.pb(i); } /*if (sz(a) == 0 || sz(b) == 0) { cout << wei << " " << sz(a) << " " << sz(b) << " " << mx-sz(cand)+1 << " " << mx << "\n"; return; }*/ divi(N,W,P,mx-sz(b),a); divi(N,W,P,mx,b); } void allValues(int N, int W, int *P) { F0R(i,N) P[i] = 0; vi cand; F0R(i,N) cand.pb(i); if (W == 2*N) { divi(N,W,P,N,cand); } else { vi cand; F0R(i,N) cand.pb(i); divi(N,W,P,N,cand); } } #ifdef LOCAL static int N, W; static int P[105]; static int maxQueries = 3200; static int numQueries; static void runGame(int F); static void grader(); int main() { grader(); return 0; } void playRound(int *B, int *R) { int i, j; int S = 0; for (i=0;i<N;++i) { if ( !(B[i] >= 0 && B[i] <= W) ) { printf("Invalid query.\n"); exit(0); } S += B[i]; } if (S > W) { printf("Invalid query.\n"); exit(0); } numQueries++; if (numQueries > maxQueries) { printf("Too many queries.\n"); exit(0); } int cache[2][205]; int num[2][205]; char taken[105][205]; for (i=0;i<205;++i) { cache[1][i] = 0; num[1][i] = 0; } for (i=0;i<N;++i) { int v = B[i]+1; int ii = i&1; int o = ii^1; for (j=0;j<=W;++j) { cache[ii][j] = cache[o][j]; num[ii][j] = num[o][j]; taken[i][j] = 0; } for (j=W;j>=v;--j) { int h = cache[o][j-v] + P[i]; int hn = num[o][j-v] + 1; if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) { cache[ii][j] = h; num[ii][j] = hn; taken[i][j] = 1; } else { taken[i][j] = 0; } } } int cur = W; for (i=N-1;i>=0;--i) { R[i] = taken[i][cur] ? (B[i] + 1) : 0; cur -= R[i]; } } static void runGame(int F) { int i; scanf("%d %d",&N,&W); for (i=0;i<N;++i) { scanf("%d",&P[i]); } numQueries = 0; if (F == 1) { printf("%d\n", minValue(N, W)); } else if (F == 2) { printf("%d\n", maxValue(N, W)); } else if (F == 3) { printf("%d\n", greaterValue(N, W)); } else if (F == 4) { int userP[105]; allValues(N, W, userP); for (i=0;i<N;i++) { printf("%d ",userP[i]); } printf("\n"); } printf("Made %d calls to playRound.\n", numQueries); } static void grader() { int i; int F, G; scanf("%d %d",&F,&G); for (i=0;i<G;i++) { runGame(F); } } #endif
#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...