#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
int B[100], R[100], N, W;
int minValue(int N, int W) {
B[0] = 1;
playRound(B, R);
for(int i = 0; i < N; ++i)
if(!R[i]) return i;
return -1;
}
int maxValue(int N, int W) {
vector<int> L;
for(int i = 0; i < N; ++i)
L.push_back(i);
while(L.size() > 1) {
int t = W / L.size();
for(int i = 0; i < N; ++i)
B[i] = R[i] = 0;
for(int i : L) B[i] = t;
playRound(B, R);
L.clear();
for(int i = 0; i < N; ++i) {
if(R[i] > t) {
L.push_back(i);
}
}
}
return L[0];
}
bool compare(int i, int j) {
int p[] = {1, 3, 6, 8};
int lo = 0, hi = 3;
for(int i = 0; i < N; ++i) B[i] = 0;
while(lo <= hi) {
int mid = lo + hi >> 1;
if(p[mid] * 2 > W) {
hi = mid - 1;
continue;
}
B[i] = B[j] = p[mid];
playRound(B, R);
bool z = R[i] > B[i];
bool o = R[j] > B[j];
if(z == o) {
if(z) lo = mid + 1;
else hi = mid - 1;
} else {
return z ? 0 : 1;
}
}
}
int greaterValue(int _N, int _W) {
N = _N; W = _W;
return compare(0, 1);
}
int Q[100];
void sort(vector<int> &a) {
if(a.size() <= 1) return;
vector<int> l, r;
int n = a.size(), k = n / 2;
for(int i = 0; i < k; i++) l.push_back(a[i]);
for(int i = k; i < n; i++) r.push_back(a[i]);
sort(l); sort(r); a.clear();
merge(l.begin(), l.end(), r.begin(), r.end(), back_inserter(a), compare);
}
void sort(vector<int> &a, int l, int r) {
if(l == r) {
Q[l] = a[0];
return;
}
int t = W / a.size();
memset(B, 0, sizeof B);
for(int i : a) B[i] = t;
playRound(B, R);
vector<int> big, small;
for(int i : a) {
if(R[i] > t) big.push_back(i);
else small.push_back(i);
}
if(big == a || small == a) {
sort(a);
for(int i = l; i <= r; i++) {
Q[i] = a[i - l];
}
return;
}
sort(small, l, l + small.size() - 1);
sort(big, r - big.size() + 1, r);
}
void allValues(int _N, int _W, int *P) {
N = _N, W = _W;
vector<int> v;
for(int i = 0; i < N; ++i)
v.push_back(i);
sort(v, 0, N - 1);
for(int i = 0; i < N; ++i)
P[Q[i]] = i + 1;
}
Compilation message
koala.cpp: In function 'bool compare(int, int)':
koala.cpp:40:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
koala.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
384 KB |
Output is correct |
| 2 |
Correct |
14 ms |
384 KB |
Output is correct |
| 3 |
Correct |
14 ms |
256 KB |
Output is correct |
| 4 |
Correct |
13 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
65 ms |
452 KB |
Output is correct |
| 2 |
Correct |
82 ms |
476 KB |
Output is correct |
| 3 |
Correct |
68 ms |
384 KB |
Output is correct |
| 4 |
Correct |
71 ms |
384 KB |
Output is correct |
| 5 |
Correct |
70 ms |
504 KB |
Output is correct |
| 6 |
Correct |
70 ms |
384 KB |
Output is correct |
| 7 |
Correct |
67 ms |
384 KB |
Output is correct |
| 8 |
Correct |
86 ms |
512 KB |
Output is correct |
| 9 |
Correct |
73 ms |
504 KB |
Output is correct |
| 10 |
Correct |
87 ms |
504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
384 KB |
Output is correct |
| 3 |
Correct |
7 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 ms |
512 KB |
Output is correct |
| 6 |
Correct |
7 ms |
384 KB |
Output is correct |
| 7 |
Correct |
7 ms |
384 KB |
Output is correct |
| 8 |
Correct |
7 ms |
384 KB |
Output is correct |
| 9 |
Correct |
7 ms |
384 KB |
Output is correct |
| 10 |
Correct |
7 ms |
384 KB |
Output is correct |
| 11 |
Correct |
10 ms |
384 KB |
Output is correct |
| 12 |
Correct |
7 ms |
384 KB |
Output is correct |
| 13 |
Correct |
10 ms |
384 KB |
Output is correct |
| 14 |
Correct |
7 ms |
384 KB |
Output is correct |
| 15 |
Correct |
7 ms |
384 KB |
Output is correct |
| 16 |
Correct |
7 ms |
384 KB |
Output is correct |
| 17 |
Correct |
7 ms |
384 KB |
Output is correct |
| 18 |
Correct |
11 ms |
384 KB |
Output is correct |
| 19 |
Correct |
7 ms |
384 KB |
Output is correct |
| 20 |
Correct |
8 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 2 |
Partially correct |
11 ms |
384 KB |
Output is partially correct |
| 3 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 4 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 5 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 6 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 7 |
Partially correct |
13 ms |
384 KB |
Output is partially correct |
| 8 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 9 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 10 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 11 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 12 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 13 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 14 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 15 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 16 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 17 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 18 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 19 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 20 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 21 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 22 |
Partially correct |
11 ms |
384 KB |
Output is partially correct |
| 23 |
Partially correct |
11 ms |
384 KB |
Output is partially correct |
| 24 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 25 |
Partially correct |
12 ms |
384 KB |
Output is partially correct |
| 26 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 27 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 28 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 29 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 30 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 31 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 32 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 33 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 34 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 35 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 36 |
Partially correct |
10 ms |
384 KB |
Output is partially correct |
| 37 |
Partially correct |
11 ms |
384 KB |
Output is partially correct |
| 38 |
Partially correct |
12 ms |
384 KB |
Output is partially correct |
| 39 |
Partially correct |
13 ms |
384 KB |
Output is partially correct |
| 40 |
Partially correct |
11 ms |
384 KB |
Output is partially correct |
