제출 #407391

#제출 시각아이디문제언어결과실행 시간메모리
407391qwerasdfzxcl코알라 (APIO17_koala)C++14
100 / 100
71 ms436 KiB
#include <bits/stdc++.h> #include "koala.h" using namespace std; int minValue(int N, int W) { // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int B[100]={0}, R[100]={0}; B[0] = 1; playRound(B, R); for (int i=0;i<N;i++) if (B[i]>=R[i]) return i; return 0; } int maxValue(int N, int W) { // TODO: Implement Subtask 2 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int B[100] = {0}, R[100] = {0}; for (int i=0;i<N;i++) B[i] = 1; playRound(B, R); int prv = 1; for (int z=1;z<4;z++){ int cnt=0; for (int i=0;i<N;i++) if (R[i]>prv) cnt++; for (int i=0;i<N;i++){ if (R[i]<=prv) B[i] = 0; else B[i] = W/cnt; } prv = W/cnt; playRound(B, R); } for (int i=0;i<N;i++) if (R[i]==12) return i; assert(0); return 0; } int greaterValue(int N, int W) { // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int B[100] = {0}, R[100] = {0}; B[0] = B[1] = 4; playRound(B, R); if (min(R[0], R[1])>=5){ B[0] = B[1] = 8; playRound(B, R); if (R[0]>R[1]) return 0; return 1; } else if (max(R[0], R[1])<=4){ B[0] = B[1] = 2; playRound(B, R); assert(R[0]<=2 || R[1]<=2); if (R[0]<=2 && R[1]<=2){ B[0] = 1, B[1] = 0; playRound(B, R); if (B[0]>=R[0]) return 1; return 0; } if (R[0]>2) return 0; return 1; } if (R[0]>4) return 0; return 1; } void dnc(int l, int r, vector<int> &v, int *P){ //printf("%d %d\n", l, r); assert(l<=r); if (l==r){ P[v[0]] = l; return; } int cur = 1; int B[100] = {0}, R[100] = {0}; while(true){ cur++; for (auto &x:v) B[x]++; int idx = r, val=0; for (;idx>=l;idx--){ if (val+cur>r-l+1) break; val += cur; } int pt1=1, pt2=idx; for (;pt1+cur-1<l && pt2>=l;pt1 += cur, pt2--){ int tmp = 0; for (int i=0;i<cur-1;i++) tmp += pt1+i; if (tmp>=pt2)break; } if (pt2>=l) break; } //printf("%d\n", B[v[0]]); //for (int i=0;i<100;i++) printf("%d ", B[i]); //printf("\n"); playRound(B, R); //for (int i=0;i<100;i++) printf("%d ", R[i]); //printf("\n"); vector<int> v1, v2; for (auto &x:v){ if (R[x]>B[x]) v2.push_back(x); else v1.push_back(x); } dnc(l, l+v1.size()-1, v1, P); dnc(l+v1.size(), r, v2, P); } void allValues(int N, int W, int *P) { if (W == 2*N) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. bool chk[100] = {0}; int B[100] = {0}, R[100] = {0}; for (int k=N;k>=2;k--){ for (int i=0;i<N;i++) B[i] = 0; int prv = W/k; for (int i=0;i<N;i++) if (!chk[i]) B[i] = prv; playRound(B, R); while(true){ int cnt=0; for (int i=0;i<N;i++) if (R[i]>prv) cnt++; assert(cnt); if (cnt==1){ for (int i=0;i<N;i++) if (R[i]>prv) P[i] = k, chk[i] = 1; break; } for (int i=0;i<N;i++){ if (R[i]>prv) B[i] = W/cnt; else B[i] = 0; } playRound(B, R); } } for (int i=0;i<N;i++) if (!chk[i]) P[i] = 1; } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. int B[100] = {0}, R[100] = {0}; for (int i=0;i<N;i++) P[i] = 0; for (int z=1;z<=50;z++){ int cnt=0; for (int i=0;i<N;i++){ if (P[i]) B[i] = 1; else if (cnt<z) B[i] = 1, cnt++; } playRound(B, R); for (int i=0;i<N;i++) if (!P[i] && R[i]<=B[i]) P[i] = z; } vector<int> v; for (int i=0;i<N;i++) if (!P[i]) v.push_back(i); dnc(51, 100, v, P); } }
#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...