#include "koala.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
const int NMAX = 1000 + 7;
int nglob;
int b[NMAX];
int r[NMAX];
int wn[NMAX];
int issmall[NMAX];
int isbig[NMAX];
void print(int a[])
{
cout << " ---> ";
for (int i = 0; i < nglob; i++)
{
cout << a[i] << " ";
}
cout << "\n";
}
void ask()
{
playRound(b, r);
for (int i = 0; i < nglob; i++)
{
wn[i] = (r[i] > b[i]);
}
}
int minValue(int n, int w)
{
nglob = n;
assert(n < NMAX);
assert(w < NMAX);
assert(n == w);
assert(n % 2 == 0);
for (int i = 0; i < n; i++)
{
b[i] = 0;
}
b[3] = 1;
ask();
int cnt_lose = 0;
for (int i = 0; i < n; i++)
{
cnt_lose += (wn[i] == 0);
}
assert(cnt_lose == 1);
for (int i = 0; i < n; i++)
{
if (wn[i] == 0)
{
return i;
}
}
assert(0);
}
int maxValue(int n, int w)
{
nglob = n;
assert(n < NMAX);
assert(w < NMAX);
assert(n == w);
assert(n % 2 == 0);
for (int i = 0; i < n; i++)
{
isbig[i] = 1;
}
for (auto& val : { 1, 2, 4, 11 })
{
for (int i = 0; i < n; i++)
{
b[i] = 0;
if (isbig[i])
{
b[i] = val;
}
}
ask();
for (int i = 0; i < n; i++)
{
isbig[i] &= wn[i];
}
}
int cntbig = 0;
for (int i = 0; i < n; i++)
{
cntbig += isbig[i];
}
assert(cntbig == 1);
for (int i = 0; i < n; i++)
{
if (isbig[i])
{
return i;
}
}
assert(0);
}
int greaterValue(int n, int w)
{
nglob = n;
assert(n < NMAX);
assert(w < NMAX);
vector<int> v;
for (int i = 1; i <= 50; i++)
{
v.push_back(i);
}
v = { 1, 2, 4, 8, 16, 32 };
int low = 0, high = (int)v.size() - 1;
while (low <= high)
{
int mid = (low + high) / 2;
int val = v[mid];
for (int i = 0; i < n; i++)
{
b[i] = 0;
}
b[0] = b[1] = val;
ask();
if (wn[0] && wn[1])
{
low = mid + 1;
continue;
}
if (!wn[0] && !wn[1])
{
high = mid - 1;
continue;
}
if (wn[0] && !wn[1]) return 0;
assert(wn[1] && !wn[0]);
return 1;
}
assert(0);
}
int funccmp(int x, int y)
{
int n = nglob;
vector<int> v;
v = { 1, 2, 4, 8, 16, 32 };
int low = 0, high = (int)v.size() - 1;
while (low <= high)
{
int mid = (low + high) / 2;
int val = v[mid];
for (int i = 0; i < n; i++)
{
b[i] = 0;
}
b[x] = b[y] = val;
ask();
if (wn[x] && wn[y])
{
low = mid + 1;
continue;
}
if (!wn[x] && !wn[y])
{
high = mid - 1;
continue;
}
if (wn[x] && !wn[y]) return 0;
assert(wn[y] && !wn[x]);
return 1;
}
assert(0);
}
int act[NMAX];
void make(vector<pair<int, int>> v)
{
int n = nglob;
for (int it = 0; it < (int)v.size(); it++)
{
for (int i = 0; i < n; i++)
{
b[i] = 0;
if (act[i])
{
b[i] = v[it].first;
}
}
ask();
assert(v[it].second == 0 || v[it].second == 1);
for (int i = 0; i < n; i++)
{
if (v[it].second == 0)
{
act[i] &= (wn[i] == 0);
}
else
{
act[i] &= (wn[i] == 1);
}
}
cout << " ---> ";
for (int i = 0; i < n; i++)
{
if (act[i])
{
cout << i << " ";
}
}
cout << "\n";
}
}
map<pair<int, int>, int > wha;
int sl[NMAX];
void dncsma(int l, int rh)
{
int n = nglob;
if (l >= rh)
{
if (l == rh)
{
//cout << "done " << l << "\n";
for (int i = 0; i < n; i++)
{
if (act[i])
{
//cout << l << " -> " << i << "\n";
sl[i] = l;
}
}
}
return;
}
vector<int> cur(n);
for (int i = 0; i < n; i++)
{
cur[i] = act[i];
}
int nractive = 0;
for (int i = 0; i < n; i++)
{
nractive += cur[i];
}
if (!wha.count({ l, rh }))
{
// cout << "bad!\n";
// exit(0);
}
assert(wha.count({ l, rh }));
int x = wha[{l, rh}];
for (int i = 0; i < n; i++)
{
b[i] = 0;
if (cur[i])
{
b[i] = x;
}
}
//cout << "wha[make_pair(" << l << ", " << r << ")] = " << x << "; ";
// cout << l << " " << r << " : " << maximums[loc] << "\n";
ask();
int sml = 0, bg = 0;
for (int i = 0; i < n; i++)
{
if (cur[i])
{
if (wn[i] == 0)
{
sml++;
}
else
{
bg++;
}
}
}
assert(sml > 0 && bg > 0);
vector<int> acu(n);
for (int i = 0; i < n; i++)
{
acu[i] = wn[i];
}
for (int i = 0; i < n; i++)
{
act[i] = cur[i] & (acu[i] == 0);
}
assert(l + sml - 1 + 1 == rh - bg + 1);
dncsma(l, l + sml - 1);
for (int i = 0; i < n; i++)
{
act[i] = cur[i] & (acu[i] == 1);
}
dncsma(rh - bg + 1, rh);
//print(act);
}
void dnc(int l, int r)
{
int n = nglob;
if (l >= r)
{
return;
}
vector<int> cur(n);
for (int i = 0; i < n; i++)
{
cur[i] = act[i];
}
int nractive = 0;
for (int i = 0; i < n; i++)
{
nractive += cur[i];
}
assert(nractive == r - l + 1);
vector<int> posi;
for (int x = 1; x <= 100; x++)
{
if (x * nractive <= 100)
{
posi.push_back(x);
}
}
assert(!posi.empty());
vector<int> maximums;
for (int it = 0; it < (int)posi.size(); it++)
{
int x = posi[it];
for (int i = 0; i < n; i++)
{
b[i] = 0;
if (cur[i])
{
b[i] = x;
}
}
ask();
int sml = 0, bg = 0;
for (int i = 0; i < n; i++)
{
if (cur[i])
{
if (wn[i] == 0)
{
sml++;
}
else
{
bg++;
}
}
}
maximums.push_back(max(sml, bg));
}
int min_max = *min_element(maximums.begin(), maximums.end());
assert(min_max < r - l + 1);
int loc = min_element(maximums.begin(), maximums.end()) - maximums.begin();
int x = posi[loc];
for (int i = 0; i < n; i++)
{
b[i] = 0;
if (cur[i])
{
b[i] = x;
}
}
cout << "wha[make_pair(" << l << ", " << r << ")] = " << x << "; ";
// cout << l << " " << r << " : " << maximums[loc] << "\n";
ask();
int sml = 0, bg = 0;
for (int i = 0; i < n; i++)
{
if (cur[i])
{
if (wn[i] == 0)
{
sml++;
}
else
{
bg++;
}
}
}
assert(sml > 0 && bg > 0);
vector<int> acu(n);
for (int i = 0; i < n; i++)
{
acu[i] = wn[i];
}
for (int i = 0; i < n; i++)
{
act[i] = cur[i] & (acu[i] == 0);
}
assert(l + sml - 1 + 1 == r - bg + 1);
dnc(l, l + sml - 1);
for (int i = 0; i < n; i++)
{
act[i] = cur[i] & (acu[i] == 1);
}
if (l == 94 && r == 96 && 0)
{
cout << "dnc " << x << " : " << sml << " and " << bg << "\n";
cout << "seg = " << r - bg + 1 << " " << r << "\n";
exit(0);
}
dnc(r - bg + 1, r);
//print(act);
}
void allValues(int n, int w, int* p)
{
nglob = n;
assert(n < NMAX);
assert(w < NMAX);
if (w == 2 * n)
{
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
else
{
//cout << "salut!\n";
assert(w == n);
vector<pair<int, int>> lol;
for (int i = 0; i < n; i++)
{
act[i] = 1;
}
wha[make_pair(0, 99)] = 1; wha[make_pair(0, 49)] = 1; wha[make_pair(0, 24)] = 1; wha[make_pair(0, 12)] = 1; wha[make_pair(0, 6)] = 1; wha[make_pair(0, 3)] = 1; wha[make_pair(0, 1)] = 1; wha[make_pair(2, 3)] = 2; wha[make_pair(4, 6)] = 2; wha[make_pair(5, 6)] = 2; wha[make_pair(7, 12)] = 2; wha[make_pair(7, 9)] = 2; wha[make_pair(8, 9)] = 3; wha[make_pair(10, 12)] = 2; wha[make_pair(11, 12)] = 3; wha[make_pair(13, 24)] = 2; wha[make_pair(13, 18)] = 3; wha[make_pair(13, 15)] = 3; wha[make_pair(14, 15)] = 3; wha[make_pair(16, 18)] = 3; wha[make_pair(17, 18)] = 4; wha[make_pair(19, 24)] = 3; wha[make_pair(19, 21)] = 3; wha[make_pair(20, 21)] = 4; wha[make_pair(22, 24)] = 3; wha[make_pair(23, 24)] = 4; wha[make_pair(25, 49)] = 2; wha[make_pair(25, 36)] = 2; wha[make_pair(25, 29)] = 3; wha[make_pair(25, 26)] = 4; wha[make_pair(27, 29)] = 4; wha[make_pair(28, 29)] = 5; wha[make_pair(30, 36)] = 3; wha[make_pair(30, 32)] = 4; wha[make_pair(31, 32)] = 5; wha[make_pair(33, 36)] = 4; wha[make_pair(33, 34)] = 5; wha[make_pair(35, 36)] = 5; wha[make_pair(37, 49)] = 3; wha[make_pair(37, 43)] = 3; wha[make_pair(37, 39)] = 4; wha[make_pair(38, 39)] = 5; wha[make_pair(40, 43)] = 5; wha[make_pair(40, 41)] = 6; wha[make_pair(42, 43)] = 6; wha[make_pair(44, 49)] = 4; wha[make_pair(44, 46)] = 4; wha[make_pair(45, 46)] = 6; wha[make_pair(47, 49)] = 5; wha[make_pair(48, 49)] = 6; wha[make_pair(50, 99)] = 2; wha[make_pair(50, 74)] = 2; wha[make_pair(50, 59)] = 3; wha[make_pair(50, 53)] = 5; wha[make_pair(50, 51)] = 6; wha[make_pair(52, 53)] = 6; wha[make_pair(54, 59)] = 5; wha[make_pair(54, 56)] = 5; wha[make_pair(55, 56)] = 6; wha[make_pair(57, 59)] = 5; wha[make_pair(58, 59)] = 7; wha[make_pair(60, 74)] = 3; wha[make_pair(60, 66)] = 4; wha[make_pair(60, 62)] = 5; wha[make_pair(61, 62)] = 7; wha[make_pair(63, 66)] = 6; wha[make_pair(63, 64)] = 7; wha[make_pair(65, 66)] = 7; wha[make_pair(67, 74)] = 4; wha[make_pair(67, 70)] = 6; wha[make_pair(67, 68)] = 7; wha[make_pair(69, 70)] = 7; wha[make_pair(71, 74)] = 6; wha[make_pair(71, 72)] = 7; wha[make_pair(73, 74)] = 7; wha[make_pair(75, 99)] = 3; wha[make_pair(75, 87)] = 4; wha[make_pair(75, 81)] = 5; wha[make_pair(75, 78)] = 6; wha[make_pair(75, 76)] = 7; wha[make_pair(77, 78)] = 8; wha[make_pair(79, 81)] = 6; wha[make_pair(80, 81)] = 8; wha[make_pair(82, 87)] = 5; wha[make_pair(82, 84)] = 6; wha[make_pair(83, 84)] = 8; wha[make_pair(85, 87)] = 6; wha[make_pair(86, 87)] = 8; wha[make_pair(88, 99)] = 4; wha[make_pair(88, 93)] = 6; wha[make_pair(88, 90)] = 6; wha[make_pair(89, 90)] = 8; wha[make_pair(91, 93)] = 6; wha[make_pair(92, 93)] = 8; wha[make_pair(94, 99)] = 6; wha[make_pair(94, 96)] = 6; wha[make_pair(95, 96)] = 8; wha[make_pair(97, 99)] = 6; wha[make_pair(98, 99)] = 8;
assert(n == 100);
dncsma(0, n - 1);
for (int i = 0; i < n; i++)
{
p[i] = sl[i];
}
return;
exit(0);
lol.push_back({ 1, 1 });
lol.push_back({ 2, 0 });
make(lol);
//for (auto& val : { 1 })
//{
// for (int i = 0; i < n; i++)
// {
// b[i] = 0;
// if (issmall[i])
// {
// b[i] = val;
// }
// }
// ask();
// for (int i = 0; i < n; i++)
// {
// issmall[i] &= !wn[i];
// }
// cout << " : ";
// for (int i = 0; i < n; i++)
// {
// if (issmall[i])
// {
// cout << i << " ";
// }
// }
// cout << "\n";
//}
return;
iota(p, p + n, 0);
sort(p, p + n, funccmp);
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
336 KB |
Output is correct |
| 2 |
Correct |
5 ms |
336 KB |
Output is correct |
| 3 |
Correct |
3 ms |
336 KB |
Output is correct |
| 4 |
Correct |
3 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
11 ms |
340 KB |
Output is correct |
| 3 |
Correct |
11 ms |
336 KB |
Output is correct |
| 4 |
Correct |
11 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
472 KB |
Output is correct |
| 2 |
Correct |
69 ms |
340 KB |
Output is correct |
| 3 |
Correct |
73 ms |
348 KB |
Output is correct |
| 4 |
Correct |
67 ms |
336 KB |
Output is correct |
| 5 |
Correct |
64 ms |
352 KB |
Output is correct |
| 6 |
Correct |
70 ms |
352 KB |
Output is correct |
| 7 |
Correct |
64 ms |
340 KB |
Output is correct |
| 8 |
Correct |
75 ms |
336 KB |
Output is correct |
| 9 |
Correct |
63 ms |
344 KB |
Output is correct |
| 10 |
Correct |
62 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
