#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
int minValue(int N, int W) {
int B[N], R[N];
for(int i=0; i<N; ++i) {
B[i] = R[i] = 0;
}
B[0] = 1;
playRound(B, R);
if(R[0]<=1) {
return 0;
}
for(int i=1; i<N; ++i) {
if(R[i]==0) return i;
}
}
int maxValue(int N, int W) {
int B[N] = {0}, R[N] = {0};
set<int>s;
for(int i=0; i<N; ++i) {
s.insert(i);
}
while(s.size()>1) {
int val = W / s.size();
memset(B, 0, sizeof B);
memset(R, 0, sizeof R);
for(int x : s) {
B[x] = val;
}
playRound(B, R);
set<int>new_s;
for(int i=0; i<N; ++i) if(R[i]>B[i]) {
if(s.count(i)) new_s.insert(i);
}
s = new_s;
}
return *s.begin();
}
int greaterValue(int N, int W) {
int B[N] = {0}, R[N] = {0};
int l = 1, r = 13;
while(l<r) {
int mid = (l+r+1)/2;
B[0] = B[1] = mid;
playRound(B, R);
if(B[0]<R[0] && B[1]<R[1]) {
l = mid;
} else if(B[0]>=R[0] && B[1]>=R[1]) {
r = mid-1;
} else {
if(R[0]>B[0]) return 0;
return 1;
}
}
}
void allValues(int N, int W, int *P) {
int B[N] = {0}, R[N] = {0};
if (W == 2*N) {
vector<vector<int>>grps(14);
fill(B, B+N, 1);
for(int i=0; i<N; ++i) {
int l = 0, r = 13;
while(l<r) {
int mid = (l+r+1)/2;
B[i] = mid+1;
playRound(B, R);
if(R[i]>B[i]) {
l = mid;
} else {
r = mid-1;
}
B[i] = 1;
}
grps[l].push_back(i);
}
vector<int>order;
for(int i=0; i<14; ++i) {
vector<int>cur;
while(!grps[i].empty()) {
fill(B, B+N, 1);
int upto = grps[i].size(), S = 0;
for(int j=0; j<grps[i].size(); ++j) {
if(S+i>W) {
upto = j;
break;
}
S += i;
B[grps[i][j]] = i+1;
}
playRound(B, R);
int mxid = -1, where;
for(int j=0; j<upto; ++j) {
if(B[grps[i][j]]<R[grps[i][j]]) {
mxid = grps[i][j];
where = j;
}
}
fill(B, B+N, 1);
S = 0;
for(int j=upto; j<grps[i].size(); ++j) {
B[grps[i][j]] = i+1;
S += i;
}
B[mxid] = i+1;
S += i;
assert(S<=W);
playRound(B, R);
if(R[mxid]>B[mxid]);
else {
for(int j=upto; j<grps[i].size(); ++j) {
if(R[grps[i][j]]>B[grps[i][j]]) {
mxid = grps[i][j];
where = j;
}
}
}
cur.push_back(mxid);
swap(grps[i].back(), grps[i][where]);
grps[i].pop_back();
if(grps[i].empty()) {
reverse(cur.begin(), cur.end());
for(int j : cur) {
order.push_back(j);
}
}
}
}
for(int i=0; i<N; ++i) {
P[order[i]] = i+1;
}
} else {
vector<vector<int>>grps(14);
for(int i=0; i<N; ++i) {
int l = 0, r = 13;
while(l<r) {
int mid = (l+r+1)/2;
B[i] = mid;
playRound(B, R);
if(R[i]>B[i]) {
l = mid;
} else {
r = mid-1;
}
B[i] = 0;
}
grps[l].push_back(i);
}
vector<int>order;
for(int i=0; i<14; ++i) {
vector<int>cur;
while(!grps[i].empty()) {
memset(B, 0, sizeof B);
int upto = grps[i].size(), S = 0;
for(int j=0; j<grps[i].size(); ++j) {
if(S+i>W) {
upto = j;
break;
}
S += i;
B[grps[i][j]] = i;
}
playRound(B, R);
int mxid = -1, where;
for(int j=0; j<upto; ++j) {
if(B[grps[i][j]]<R[grps[i][j]]) {
mxid = grps[i][j];
where = j;
}
}
memset(B, 0, sizeof B);
S = 0;
for(int j=upto; j<grps[i].size(); ++j) {
B[grps[i][j]] = i;
S += i;
}
B[mxid] = i;
S += i;
assert(S<=W);
playRound(B, R);
if(R[mxid]>B[mxid]);
else {
for(int j=upto; j<grps[i].size(); ++j) {
if(R[grps[i][j]]>B[grps[i][j]]) {
mxid = grps[i][j];
where = j;
}
}
}
cur.push_back(mxid);
swap(grps[i].back(), grps[i][where]);
grps[i].pop_back();
if(grps[i].empty()) {
reverse(cur.begin(), cur.end());
for(int j : cur) {
order.push_back(j);
}
}
}
}
for(int i=0; i<N; ++i) {
P[order[i]] = i+1;
}
}
}
Compilation message
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:103:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j=0; j<grps[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~
koala.cpp:124:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j=upto; j<grps[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~
koala.cpp:135:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int j=upto; j<grps[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~
koala.cpp:184:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int j=0; j<grps[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~
koala.cpp:205:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | for(int j=upto; j<grps[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~
koala.cpp:216:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | for(int j=upto; j<grps[i].size(); ++j) {
| ~^~~~~~~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
20 | }
| ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
70 | }
| ^
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:224:51: warning: 'where' may be used uninitialized in this function [-Wmaybe-uninitialized]
224 | swap(grps[i].back(), grps[i][where]);
| ^
koala.cpp:143:51: warning: 'where' may be used uninitialized in this function [-Wmaybe-uninitialized]
143 | swap(grps[i].back(), grps[i][where]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
208 KB |
Output is correct |
| 2 |
Correct |
4 ms |
208 KB |
Output is correct |
| 3 |
Correct |
4 ms |
208 KB |
Output is correct |
| 4 |
Correct |
5 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
208 KB |
Output is correct |
| 2 |
Correct |
14 ms |
208 KB |
Output is correct |
| 3 |
Correct |
14 ms |
212 KB |
Output is correct |
| 4 |
Correct |
13 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
320 KB |
Output is correct |
| 2 |
Partially correct |
45 ms |
340 KB |
Output is partially correct |
| 3 |
Correct |
39 ms |
328 KB |
Output is correct |
| 4 |
Correct |
39 ms |
312 KB |
Output is correct |
| 5 |
Partially correct |
41 ms |
324 KB |
Output is partially correct |
| 6 |
Correct |
41 ms |
328 KB |
Output is correct |
| 7 |
Partially correct |
39 ms |
336 KB |
Output is partially correct |
| 8 |
Correct |
46 ms |
436 KB |
Output is correct |
| 9 |
Correct |
39 ms |
328 KB |
Output is correct |
| 10 |
Correct |
45 ms |
324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
16 ms |
312 KB |
Output is partially correct |
| 2 |
Partially correct |
15 ms |
320 KB |
Output is partially correct |
| 3 |
Partially correct |
29 ms |
312 KB |
Output is partially correct |
| 4 |
Partially correct |
17 ms |
208 KB |
Output is partially correct |
| 5 |
Partially correct |
23 ms |
208 KB |
Output is partially correct |
| 6 |
Partially correct |
21 ms |
208 KB |
Output is partially correct |
| 7 |
Partially correct |
16 ms |
308 KB |
Output is partially correct |
| 8 |
Partially correct |
16 ms |
320 KB |
Output is partially correct |
| 9 |
Partially correct |
16 ms |
312 KB |
Output is partially correct |
| 10 |
Partially correct |
15 ms |
208 KB |
Output is partially correct |
| 11 |
Partially correct |
16 ms |
316 KB |
Output is partially correct |
| 12 |
Partially correct |
15 ms |
316 KB |
Output is partially correct |
| 13 |
Partially correct |
15 ms |
312 KB |
Output is partially correct |
| 14 |
Partially correct |
16 ms |
308 KB |
Output is partially correct |
| 15 |
Partially correct |
17 ms |
316 KB |
Output is partially correct |
| 16 |
Partially correct |
19 ms |
440 KB |
Output is partially correct |
| 17 |
Partially correct |
19 ms |
312 KB |
Output is partially correct |
| 18 |
Partially correct |
16 ms |
312 KB |
Output is partially correct |
| 19 |
Partially correct |
17 ms |
316 KB |
Output is partially correct |
| 20 |
Partially correct |
17 ms |
312 KB |
Output is partially correct |
| 21 |
Partially correct |
16 ms |
316 KB |
Output is partially correct |
| 22 |
Partially correct |
22 ms |
316 KB |
Output is partially correct |
| 23 |
Partially correct |
15 ms |
312 KB |
Output is partially correct |
| 24 |
Partially correct |
15 ms |
316 KB |
Output is partially correct |
| 25 |
Partially correct |
16 ms |
316 KB |
Output is partially correct |
| 26 |
Partially correct |
16 ms |
316 KB |
Output is partially correct |
| 27 |
Partially correct |
16 ms |
208 KB |
Output is partially correct |
| 28 |
Partially correct |
18 ms |
316 KB |
Output is partially correct |
| 29 |
Partially correct |
16 ms |
312 KB |
Output is partially correct |
| 30 |
Partially correct |
21 ms |
312 KB |
Output is partially correct |
| 31 |
Partially correct |
16 ms |
208 KB |
Output is partially correct |
| 32 |
Partially correct |
16 ms |
208 KB |
Output is partially correct |
| 33 |
Partially correct |
15 ms |
308 KB |
Output is partially correct |
| 34 |
Partially correct |
16 ms |
208 KB |
Output is partially correct |
| 35 |
Partially correct |
16 ms |
316 KB |
Output is partially correct |
| 36 |
Partially correct |
16 ms |
312 KB |
Output is partially correct |
| 37 |
Partially correct |
17 ms |
208 KB |
Output is partially correct |
| 38 |
Partially correct |
16 ms |
208 KB |
Output is partially correct |
| 39 |
Partially correct |
16 ms |
208 KB |
Output is partially correct |
| 40 |
Partially correct |
15 ms |
312 KB |
Output is partially correct |
