제출 #404259

#제출 시각아이디문제언어결과실행 시간메모리
404259Haruto810198코알라 (APIO17_koala)C++17
100 / 100
57 ms436 KiB
#include <bits/stdc++.h> #include "koala.h" using namespace std; //#define int long long #define double long double #define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d)) #define szof(x) ((x).size()) #define vi vector<int> #define pii pair<int,int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair const int INF = 2147483647; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; int B[100]; int R[100]; int res[100]; 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. FOR(i,0,N-2,1){ B[i] = 0; } B[N-1] = 1; playRound(B, R); int ret = 0; FOR(i,0,N-1,1){ if(R[i]<=B[i]){ ret = i; } } return ret; } 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. bool isMax[N]; /// Round 0: 100 -> 50 /// Round 1: 50 -> 25 /// Round 2: 25 -> 9 /// Round 3: 9 -> 1 int Maxstone[4] = {1, 2, 4, 11}; FOR(i,0,N-1,1){ isMax[i] = 1; } FOR(Round,0,3,1){ FOR(i,0,N-1,1){ if(isMax[i]==1){ B[i] = Maxstone[Round]; } else{ B[i] = 0; } } playRound(B, R); FOR(i,0,N-1,1){ if(R[i]>B[i] and isMax[i]==1){ isMax[i] = 1; } else{ isMax[i] = 0; } } } FOR(i,0,N-1,1){ if(isMax[i]){ return i; } } 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. FOR(i,2,N-1,1){ B[i] = 0; } int lb=1, rb=14, mid; while(lb<rb){ mid = (lb+rb) / 2; B[0] = B[1] = mid; playRound(B, R); if(R[0]>B[0] and R[1]>B[1]){ lb = mid+1; } else if(R[0]<=B[0] and R[1]<=B[1]){ rb = mid-1; } else{ if(R[0]>B[0]){ return 0; } else{ return 1; } } } return 0; } bool cmp(int n1, int n2){ FOR(i,0,99,1){ B[i] = 0; } B[n1] = B[n2] = 100; playRound(B, R); return (R[n1]<R[n2]); } bool testPlayRound(int Min, int Max, int ccnt) { //cerr<<"testPlayRound "<<Min<<"~"<<Max<<" ccnt="<<ccnt; int i, j; const int N=100, W=100; int cache[2][205]; int num[2][205]; char taken[105][205]; int A[100]; for (i=0;i<205;++i) { cache[1][i] = 0; num[1][i] = 0; } FOR(i,0,99,1){ A[i] = i+1; B[i] = (Min<=A[i] and A[i]<=Max) ? ccnt : 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] + A[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]; } int Maxcnt = 0; FOR(i,Min-1,Max-1,1){ if(R[i] > B[i]){ Maxcnt++; } } //cerr<<" Maxcnt="<<Maxcnt<<endl; return (0<Maxcnt and Maxcnt<(Max-Min+1)); } void split(bool *arr, int Min){ int cnt = 0; FOR(i,0,99,1){ cnt += arr[i]; } int Max = Min + cnt - 1; //cerr<<"split "<<Min<<" ~ "<<Max<<endl; if(cnt==1){ FOR(i,0,99,1){ if(arr[i]==1){ res[i] = Min; } } return; } int ccnt = 1; while(1){ if(testPlayRound(Min, Max, ccnt)){ bool arrmin[100], arrMax[100]; int mincnt=0, Maxcnt=0; FOR(i,0,99,1){ if(arr[i]==1){ B[i] = ccnt; } else{ B[i] = 0; } } playRound(B, R); FOR(i,0,99,1){ if(arr[i]==1){ if(R[i] > B[i]){ arrMax[i] = 1; arrmin[i] = 0; Maxcnt++; } else{ arrMax[i] = 0; arrmin[i] = 1; mincnt++; } } else{ arrMax[i] = 0; arrmin[i] = 0; } } split(arrmin, Min); split(arrMax, Min + mincnt); break; } ccnt++; } } 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. int rk[100]; FOR(i,0,99,1){ rk[i] = i; } stable_sort(rk,rk+100,cmp); FOR(i,0,99,1){ P[rk[i]] = i + 1; } } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. bool arr[100]; FOR(i,0,99,1){ arr[i] = 1; } split(arr, 1); FOR(i,0,99,1){ P[i] = res[i]; } } }
#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...