This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 + 1;
}
}
}
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";
#ifdef ONPC
cout << "if(l == " << l << " && rh == " << rh << ") exit(0);" << "\n";
#endif
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);
#ifndef ONPC
//if (l == 2 && rh == 3) exit(0);
#endif
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 <= 200)
{
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.
for (int i = 0; i < n; i++)
{
act[i] = 1;
}
wha[make_pair(0, 99)] = 2; wha[make_pair(0, 33)] = 5; wha[make_pair(0, 11)] = 16; wha[make_pair(0, 5)] = 26; wha[make_pair(0, 2)] = 34; wha[make_pair(1, 2)] = 51; wha[make_pair(3, 5)] = 35; wha[make_pair(4, 5)] = 52; wha[make_pair(6, 11)] = 27; wha[make_pair(6, 8)] = 35; wha[make_pair(7, 8)] = 52; wha[make_pair(9, 11)] = 35; wha[make_pair(10, 11)] = 53; wha[make_pair(12, 33)] = 9; wha[make_pair(12, 21)] = 19; wha[make_pair(12, 16)] = 27; wha[make_pair(12, 13)] = 53; wha[make_pair(14, 16)] = 35; wha[make_pair(15, 16)] = 53; wha[make_pair(17, 21)] = 27; wha[make_pair(17, 18)] = 53; wha[make_pair(19, 21)] = 36; wha[make_pair(20, 21)] = 53; wha[make_pair(22, 33)] = 16; wha[make_pair(22, 27)] = 28; wha[make_pair(22, 24)] = 36; wha[make_pair(23, 24)] = 54; wha[make_pair(25, 27)] = 36; wha[make_pair(26, 27)] = 54; wha[make_pair(28, 33)] = 28; wha[make_pair(28, 30)] = 36; wha[make_pair(29, 30)] = 54; wha[make_pair(31, 33)] = 36; wha[make_pair(32, 33)] = 54; wha[make_pair(34, 99)] = 3; wha[make_pair(34, 54)] = 9; wha[make_pair(34, 42)] = 19; wha[make_pair(34, 37)] = 37; wha[make_pair(34, 35)] = 54; wha[make_pair(36, 37)] = 55; wha[make_pair(38, 42)] = 28; wha[make_pair(38, 39)] = 55; wha[make_pair(40, 42)] = 37; wha[make_pair(41, 42)] = 55; wha[make_pair(43, 54)] = 15; wha[make_pair(43, 47)] = 28; wha[make_pair(43, 44)] = 55; wha[make_pair(45, 47)] = 37; wha[make_pair(46, 47)] = 55; wha[make_pair(48, 54)] = 23; wha[make_pair(48, 50)] = 37; wha[make_pair(49, 50)] = 55; wha[make_pair(51, 54)] = 37; wha[make_pair(51, 52)] = 55; wha[make_pair(53, 54)] = 55; wha[make_pair(55, 99)] = 4; wha[make_pair(55, 67)] = 15; wha[make_pair(55, 60)] = 29; wha[make_pair(55, 57)] = 37; wha[make_pair(56, 57)] = 56; wha[make_pair(58, 60)] = 37; wha[make_pair(59, 60)] = 56; wha[make_pair(61, 67)] = 23; wha[make_pair(61, 63)] = 37; wha[make_pair(62, 63)] = 56; wha[make_pair(64, 67)] = 38; wha[make_pair(64, 65)] = 56; wha[make_pair(66, 67)] = 56; wha[make_pair(68, 99)] = 6; wha[make_pair(68, 79)] = 15; wha[make_pair(68, 72)] = 29; wha[make_pair(68, 69)] = 56; wha[make_pair(70, 72)] = 38; wha[make_pair(71, 72)] = 56; wha[make_pair(73, 79)] = 23; wha[make_pair(73, 75)] = 38; wha[make_pair(74, 75)] = 56; wha[make_pair(76, 79)] = 38; wha[make_pair(76, 77)] = 56; wha[make_pair(78, 79)] = 57; wha[make_pair(80, 99)] = 10; wha[make_pair(80, 87)] = 24; wha[make_pair(80, 83)] = 38; wha[make_pair(80, 81)] = 57; wha[make_pair(82, 83)] = 57; wha[make_pair(84, 87)] = 38; wha[make_pair(84, 85)] = 57; wha[make_pair(86, 87)] = 57; wha[make_pair(88, 99)] = 15; wha[make_pair(88, 92)] = 29; wha[make_pair(88, 89)] = 57; wha[make_pair(90, 92)] = 38; wha[make_pair(91, 92)] = 57; wha[make_pair(93, 99)] = 24; wha[make_pair(93, 95)] = 38; wha[make_pair(94, 95)] = 57; wha[make_pair(96, 99)] = 39; wha[make_pair(96, 97)] = 57; wha[make_pair(98, 99)] = 57;
dncsma(0, n - 1);
for (int i = 0; i < n; i++)
{
p[i] = sl[i];
}
return;
}
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)] = 1; wha[make_pair(4, 6)] = 1; wha[make_pair(5, 6)] = 2; wha[make_pair(7, 12)] = 2; wha[make_pair(7, 9)] = 2; wha[make_pair(8, 9)] = 2; wha[make_pair(10, 12)] = 2; wha[make_pair(11, 12)] = 3; wha[make_pair(13, 24)] = 2; wha[make_pair(13, 18)] = 2; wha[make_pair(13, 14)] = 3; wha[make_pair(15, 18)] = 3; wha[make_pair(15, 16)] = 3; wha[make_pair(17, 18)] = 3; 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, 37)] = 2; wha[make_pair(25, 29)] = 3; wha[make_pair(25, 26)] = 4; wha[make_pair(27, 29)] = 3; wha[make_pair(28, 29)] = 4; wha[make_pair(30, 37)] = 3; wha[make_pair(30, 33)] = 4; wha[make_pair(30, 31)] = 5; wha[make_pair(32, 33)] = 5; wha[make_pair(34, 37)] = 4; wha[make_pair(34, 35)] = 5; wha[make_pair(36, 37)] = 5; wha[make_pair(38, 49)] = 3; wha[make_pair(38, 43)] = 4; wha[make_pair(38, 40)] = 4; wha[make_pair(39, 40)] = 5; wha[make_pair(41, 43)] = 4; wha[make_pair(42, 43)] = 5; wha[make_pair(44, 49)] = 4; wha[make_pair(44, 46)] = 4; wha[make_pair(45, 46)] = 6; wha[make_pair(47, 49)] = 4; 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)] = 4; wha[make_pair(54, 56)] = 5; wha[make_pair(55, 56)] = 6; wha[make_pair(57, 59)] = 5; wha[make_pair(58, 59)] = 6; wha[make_pair(60, 74)] = 3; wha[make_pair(60, 66)] = 4; wha[make_pair(60, 62)] = 5; wha[make_pair(61, 62)] = 6; wha[make_pair(63, 66)] = 5; wha[make_pair(63, 64)] = 7; wha[make_pair(65, 66)] = 7; wha[make_pair(67, 74)] = 4; wha[make_pair(67, 70)] = 5; 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)] = 4; wha[make_pair(75, 77)] = 6; wha[make_pair(76, 77)] = 7; wha[make_pair(78, 81)] = 6; wha[make_pair(78, 79)] = 7; wha[make_pair(80, 81)] = 7; wha[make_pair(82, 87)] = 5; wha[make_pair(82, 84)] = 6; wha[make_pair(83, 84)] = 7; wha[make_pair(85, 87)] = 6; wha[make_pair(86, 87)] = 8; wha[make_pair(88, 99)] = 4; wha[make_pair(88, 93)] = 5; 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 |
---|
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... |