이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |