#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
int B[105], R[105];
int minValue(int N, int W) {
B[0] = 1;
playRound(B, R);
if(R[0] == 2)for(int i = 0; i < N; i++)if(R[i] == 0)return i;
return 0;
}
vector<int> search_set = {1, 2, 3, 5, 8};
int maxValue(int N, int W) {
vector<int> vec = {1, 2, 4, 11};
vector<int> good(N);
iota(good.begin(), good.end(), 0);
for(auto v: vec){
fill(B, B + N, 0);
for(auto id: good)B[id] = v;
playRound(B, R);
good.clear();
for(int i = 0; i < N; i++)if(R[i] > v)good.push_back(i);
}
return good.back();
}
int greaterValue(int N, int W) {
int l = 0, r = search_set.size()-1;
while(l <= r){
int md = (l+r)>>1;
int mid = search_set[md];
B[0] = B[1] = mid;
playRound(B, R);
if (R[0] > mid and R[1] <= mid) return 0;
if (R[1] > mid and R[0] <= mid) return 1;
if(R[0] > mid && R[1] > mid)l = md + 1;
else r = md - 1;
}
return 0;
// k p0 <= sum (k+1)so dau tien < p1
}
int n;
// 1-3, 3-9, 6-18, 15-45, 36-100
int bound[9][2] = {
{0, 0},
{0, 4},
{2, 10},
{5, 19},
{9, 31},
{14, 46},
{20, 64},
{27, 85},
{35, 101}
};
int cbound[105][2];
int cnt[105][2];
bool recmp[105][105];
int ans[105];
bool cmp(int a, int b){
assert(a != b);
if(recmp[a][b])return 1;
if(recmp[b][a])return 0;
int la = max(cnt[a][0] - 1, cbound[a][0]), ra = min(100 - cnt[a][1], cbound[a][1]);
int lb = max(cnt[b][0] - 1, cbound[b][0]), rb = min(100 - cnt[b][1], cbound[b][1]);
if(la >= rb){
cnt[a][0]++;
cnt[b][1]++;
recmp[b][a] = 1;
cbound[a][0] = max(cbound[a][0], cbound[b][0]);
cbound[b][1] = min(cbound[b][1], cbound[a][1]);
return 0;
}
if(lb >= ra){
recmp[a][b] = 1;
cnt[b][0]++;
cnt[a][1]++;
cbound[b][0] = max(cbound[b][0], cbound[a][0]);
cbound[a][1] = min(cbound[a][1], cbound[b][1]);
return 1;
}
int l = -1, r = -1;
for(int i = 0; i < search_set.size(); i++){
if(bound[search_set[i]][0] >= min(ra, rb) || bound[search_set[i]][1] <= max(la, lb))continue;
if(l == -1)l = i;
r = i;
}
while(l <= r){
int md = (l+r)>>1;
int mid = search_set[md];
fill(B, B+n, 0);
B[a] = B[b] = mid;
playRound(B, R);
// cout << mid << " " << R[a] << " " << R[b] << endl;
if (R[a] > mid and R[b] <= mid) {
cnt[a][0]++;
cnt[b][1]++;
recmp[b][a] = 1;
cbound[a][0] = max(cbound[a][0], cbound[b][0]);
cbound[b][1] = min(cbound[b][1], cbound[a][1]);
return 0;
}
if (R[b] > mid and R[a] <= mid) {
cnt[b][0]++;
cnt[a][1]++;
recmp[a][b] = 1;
cbound[b][0] = max(cbound[b][0], cbound[a][0]);
cbound[a][1] = min(cbound[a][1], cbound[b][1]);
return 1;
}
if(R[a] > mid && R[b] > mid){
l = md + 1;
cbound[a][0] = max(cbound[a][0], bound[mid][1]);
cbound[b][0] = max(cbound[b][0], bound[mid][1]);
}
else {
r = md - 1;
cbound[a][1] = min(cbound[a][1], bound[mid][0]);
cbound[b][1] = min(cbound[b][1], bound[mid][0]);
}
}
assert(false);
return 0;
}
bool cmp_subtask_4(int a, int b){
fill(B, B+n, 0);
B[a] = B[b] = n;
playRound(B, R);
return R[a] < R[b];
}
mt19937 rng_lmao(69420);
pair<int, int> vis[105][105];
void allValues(int N, int W, int *P) {
n = N;
if (W == 2*N) {
vector<int> vec(N);
iota(vec.begin(), vec.end(), 0);
stable_sort(vec.begin(), vec.end(), cmp_subtask_4);
for(int i = 0; i < N; i++)P[vec[i]] = i+1;
} else {
vis[1][101] = {1, 51};
vis[1][51] = {1, 26};
vis[1][26] = {1, 14};
vis[1][14] = {1, 8};
vis[1][8] = {1, 5};
vis[1][5] = {1, 3};
vis[1][3] = {1, 2};
vis[3][5] = {2, 4};
vis[5][8] = {2, 7};
vis[5][7] = {3, 6};
vis[8][14] = {2, 11};
vis[8][11] = {3, 10};
vis[8][10] = {4, 9};
vis[11][14] = {4, 13};
vis[11][13] = {5, 12};
vis[14][26] = {2, 20};
vis[14][20] = {3, 18};
vis[14][18] = {4, 17};
vis[14][17] = {5, 16};
vis[14][16] = {5, 15};
vis[18][20] = {6, 19};
vis[20][26] = {4, 24};
vis[20][24] = {6, 23};
vis[20][23] = {7, 22};
vis[20][22] = {6, 21};
vis[24][26] = {7, 25};
vis[26][51] = {2, 39};
vis[26][39] = {3, 34};
vis[26][34] = {4, 31};
vis[26][31] = {6, 30};
vis[26][30] = {7, 29};
vis[26][29] = {8, 28};
vis[26][28] = {7, 27};
vis[31][34] = {9, 33};
vis[31][33] = {8, 32};
vis[34][39] = {7, 38};
vis[34][38] = {9, 37};
vis[34][37] = {9, 36};
vis[34][36] = {8, 35};
vis[39][51] = {4, 47};
vis[39][47] = {5, 45};
vis[39][45] = {7, 44};
vis[39][44] = {8, 43};
vis[39][43] = {10, 42};
vis[39][42] = {10, 41};
vis[39][41] = {9, 40};
vis[45][47] = {10, 46};
vis[47][51] = {12, 50};
vis[47][50] = {11, 49};
vis[47][49] = {10, 48};
vis[51][101] = {2, 76};
vis[51][76] = {3, 66};
vis[51][66] = {4, 61};
vis[51][61] = {6, 58};
vis[51][58] = {8, 57};
vis[51][57] = {9, 56};
vis[51][56] = {11, 55};
vis[51][55] = {12, 54};
vis[51][54] = {11, 53};
vis[51][53] = {10, 52};
vis[58][61] = {12, 60};
vis[58][60] = {11, 59};
vis[61][66] = {13, 65};
vis[61][65] = {13, 64};
vis[61][64] = {12, 63};
vis[61][63] = {11, 62};
vis[66][76] = {7, 74};
vis[66][74] = {9, 73};
vis[66][73] = {10, 72};
vis[66][72] = {12, 71};
vis[66][71] = {14, 70};
vis[66][70] = {14, 69};
vis[66][69] = {13, 68};
vis[66][68] = {12, 67};
vis[74][76] = {12, 75};
vis[76][101] = {4, 92};
vis[76][92] = {5, 87};
vis[76][87] = {7, 84};
vis[76][84] = {10, 83};
vis[76][83] = {11, 82};
vis[76][82] = {13, 81};
vis[76][81] = {16, 80};
vis[76][80] = {15, 79};
vis[76][79] = {13, 78};
vis[76][78] = {12, 77};
vis[84][87] = {14, 86};
vis[84][86] = {13, 85};
vis[87][92] = {16, 91};
vis[87][91] = {15, 90};
vis[87][90] = {14, 89};
vis[87][89] = {13, 88};
vis[92][101] = {11, 100};
vis[92][100] = {12, 99};
vis[92][99] = {14, 98};
vis[92][98] = {16, 97};
vis[92][97] = {17, 96};
vis[92][96] = {16, 95};
vis[92][95] = {15, 94};
vis[92][94] = {14, 93};
auto dfs = [&](auto self, vector<int> idx, int l, int r) -> void {
if (l + 1 == r) {
ans[idx.front()] = l;
return;
}
fill(B, B + n, 0);
int val = vis[l][r].first;
// cout << l << " " << r << " " << val << endl;
for (int idx_ : idx) B[idx_] = val;
playRound(B, R);
vector<int> left, right;
for (int idx_ : idx) {
if (R[idx_] > val) right.emplace_back(idx_);
else left.emplace_back(idx_);
}
// cout << l << " " << r << " " << l + isz(left) << " " << r - isz(right) << " " << vis[l][r].second << endl;
assert(l + isz(left) == vis[l][r].second);
assert(r - isz(right) == vis[l][r].second);
self(self, left, l, l + isz(left));
self(self, right, r - isz(right), r);
};
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
dfs(dfs, idx, 1, n + 1);
}
}
Compilation message
koala.cpp: In function 'bool cmp(int, int)':
koala.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < search_set.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from koala.cpp:2:
koala.cpp: In lambda function:
koala.cpp:268:20: error: there are no arguments to 'isz' that depend on a template parameter, so a declaration of 'isz' must be available [-fpermissive]
268 | assert(l + isz(left) == vis[l][r].second);
| ^~~
koala.cpp:268:20: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
koala.cpp:269:20: error: there are no arguments to 'isz' that depend on a template parameter, so a declaration of 'isz' must be available [-fpermissive]
269 | assert(r - isz(right) == vis[l][r].second);
| ^~~
koala.cpp:270:33: error: there are no arguments to 'isz' that depend on a template parameter, so a declaration of 'isz' must be available [-fpermissive]
270 | self(self, left, l, l + isz(left));
| ^~~
koala.cpp:271:31: error: there are no arguments to 'isz' that depend on a template parameter, so a declaration of 'isz' must be available [-fpermissive]
271 | self(self, right, r - isz(right), r);
| ^~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from koala.cpp:2:
koala.cpp: In instantiation of 'allValues(int, int, int*)::<lambda(auto:1, std::vector<int>, int, int)> [with auto:1 = allValues(int, int, int*)::<lambda(auto:1, std::vector<int>, int, int)>]':
koala.cpp:275:27: required from here
koala.cpp:268:23: error: 'isz' was not declared in this scope
268 | assert(l + isz(left) == vis[l][r].second);
| ~~~^~~~~~
koala.cpp:269:23: error: 'isz' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
269 | assert(r - isz(right) == vis[l][r].second);
| ~~~^~~~~~~
koala.cpp:270:36: error: 'isz' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
270 | self(self, left, l, l + isz(left));
| ~~~^~~~~~
koala.cpp:271:34: error: 'isz' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
271 | self(self, right, r - isz(right), r);
| ~~~^~~~~~~
