#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, a[N], b[N];
int cnt = 0;
vector<int> er(vector<int> a, int x){
vector<int> b;
for(auto it : a) if(it != x) b.pb(it);
return b;
}
int Query(int x, int y){
cnt++;
//cout << x << " " << y << " " << b[x] << b[y] << "\n";
if(b[x] < (b[y] - 1)) return 0;
if(b[x] == (b[y] + 1)) return 0;
return 1;
}
map<ii, bool> mp;
/*
int Querry(int x, int y){
if(mp.find({x, y}) != mp.end()) return mp[{x, y}];
int temp = Query(x, y);
mp[{x, y}] = temp;
mp[{y, x}] = 1 - temp;
return temp;
}*/
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
temp = (temp + (r - l + 1)) % (r - l + 1);
return temp + l;
}
int deg[N];
void solve_brute(vector<int> x, int l, int r){
if(!x.size()) return;
assert(x.size() == (r - l + 1));
if(x.size() == 1){
a[x[0]] = l;
return;
}
assert(x.size() != 3);
for(int i = 0; i < x.size(); i++) deg[x[i]] = 0;
for(int i = 0; i < x.size(); i++){
for(int j = i + 1; j < x.size(); j++){
Querry(x[i], x[j]);
//cout << i << " " << j << " " << b[x[i]] << " " << b[x[j]] << " " << mp[{x[i], x[j]}] << "\n";
if(mp[{x[i], x[j]}]) deg[x[i]]++;
else deg[x[j]]++;
}
}
if(x.size() == 2){
if(!mp[{x[0], x[1]}]){
a[x[0]] = r, a[x[1]] = l;
}
else{
a[x[1]] = r, a[x[0]] = l;
}
return;
}
int mn0 = -1, mn1, mx0 = -1, mx1;
//cout << x.size() << "\n";
for(auto it : x){
if(deg[it] >= 2 && deg[it] <= x.size() - 3){
a[it] = l + deg[it];
}
if(deg[it] == 1){
if(mn0 == -1) mn0 = it;
else mn1 = it;
}
if(deg[it] == x.size() - 2){
if(mx0 == -1) mx0 = it;
else mx1 = it;
}
//cout << deg[it] << " ";
}/*
cout << "\n";
for(auto it : x) cout << b[it] << " ";
cout << "\n";
cout << Querry(b[2], b[4]) << "\n";
cout << mn0 << " " << mn1 << " " << mx0 << " " << mx1 << "\n";
if(min({mn0, mn1, mx0, mx1}) < 0) exit(0);*/
//cout << mn0 << " " << mn1 << "\n";
if(mp[{mn0, mn1}]){
a[mn0] = l; a[mn1] = l + 1;
}
else{
a[mn0] = l + 1; a[mn1] = l;
}
if(mp[{mx0, mx1}]){
a[mx0] = r - 1; a[mx1] = r;
}
else{
a[mx0] = r; a[mx1] = r - 1;
}
}
int med(int a, int b, int c){
int cnt[3];
cnt[0] = cnt[1] = cnt[2] = 0;
if(Querry(a, b)) cnt[0]++; else cnt[1]++;
if(Querry(a, c)) cnt[0]++; else cnt[2]++;
if(cnt[0] == 1) return a;
if(Querry(b, c)) cnt[1]++; else cnt[2]++;
if(cnt[1] == 1) return b;
else return c;
}
void solve(vector<int> x, int l, int r){
//for(auto it : x) assert(b[it] >= l && b[it] <= r);
shuffle(x.begin(), x.end(), default_random_engine(7405));
if(x.size() <= 10){
solve_brute(x, l, r);
return;
}
int temp;
int iter = 0;
temp = -1;
vector<int> can = x;
can.resize((x.size() * 3) / 4);
while(can.size() > 1){
while(can.size() > 1 && (can.size() % 3)) can.pop_back();
if(can.size() == 1) break;
vector<int> can2;
for(int i = 0; i < can.size(); i += 3){
can2.pb(med(can[i], can[i + 1], can[i + 2]));
}
can = can2;
}
temp = can[0];
//cout << l << " " << r << " " << b[temp] << "\n";
//assert(b[temp] > (l + 1) && b[temp] < (r - 1));
/*
if(la.size() < 2){
for(auto it : sm){
int cnt = 0;
for(auto it2 : sm) if(it != it2 && Querry(it, it2)) cnt++;
if(cnt >= 4 && cnt <= 6){
temp = it;
break;
}
}
}*/
//cout << l << " " << r << " " << temp << "\n";
//if(cnt1 < 2 || cnt2 < 2) continue;
//break;
//cout << temp << "\n";
vector<int> vc1, vc2;
for(auto it : x){
if(it == temp) continue;
if(Query(temp, it)) vc1.pb(it);
else vc2.pb(it);
}
while(vc1.size() == 1 || vc2.size() == 1){
vc1.clear(), vc2.clear();
temp = x[rnd(0, (int)x.size() - 1)];
for(auto it : x){
if(it == temp) continue;
if(Query(temp, it)) vc1.pb(it);
else vc2.pb(it);
}
}
//cout << vc1.size() << " " << vc2.size() << "\n";
//cout << temp << " " << l + vc1.size() << "\n";
a[temp] = l + vc1.size();
int w1 = vc1[0], w2 = vc2[0];
for(auto it : vc1){
if(it == w1) continue;
if(Querry(it, w1)) w1 = it;
}
shuffle(vc2.begin(), vc2.end(), default_random_engine(2005));
ii cans = {-1, -1};
for(auto it : vc2){
if(Querry(w1, it)){
if(cans.fi == -1) cans.fi = it;
else{
cans.se = it;
break;
}
}
//if(it == w2) continue;
//if(Querry(w2, it)) w2 = it;
}
w2 = (Querry(cans.fi, cans.se) ? cans.se : cans.fi);
bool ck1 = 0, ck2 = 0;
a[w1] = l + vc1.size() + 1;
a[w2] = l + vc1.size() - 1;
vc1 = er(vc1, w1);
vc2 = er(vc2, w2);
//vc1 = er(vc1, w1);
//vc2 = er(vc2, w2);
if(vc1.size() == 3) vc1.pb(w2);
if(vc2.size() == 3) vc2.pb(w1);
solve(vc1, l, l + vc1.size() - 1);
solve(vc2, r - vc2.size() + 1, r);
}
/*
void solve(vector<int> x, int l, int r){
if(x.size() <= 4){
solve_brute(x, l, r);
return;
}
int temp;
vector<int> vc1, vc2;
while(1){
temp = x[rnd(0, x.size() - 1)];
vc1.clear(), vc2.clear();
for(auto it : x){
if(it == temp) continue;
if(!Query(it, temp)) vc1.pb(it);
else vc2.pb(it);
}
assert(vc1.size() && vc2.size());
if(vc1.size() == 1 || vc2.size() == 1) continue;
if(vc1.size() == 4 || vc2.size() == 4) continue;
break;
}
//cout << temp << " " << l + vc1.size() << "\n";
a[temp] = l + vc1.size();
int w1 = vc1[0], w2 = vc2[0];
for(auto it : vc1){
if(it == w1) continue;
if(Query(it, w1)) w1 = it;
}
for(auto it : vc2){
if(it == w2) continue;
if(Query(w2, it)) w2 = it;
}
bool ck1 = 0, ck2 = 0;
a[w1] = l + vc1.size() + 1;
a[w2] = l + vc1.size() - 1;
vc1 = er(vc1, w1);
vc2 = er(vc2, w2);
solve(vc1, l, l + vc1.size() - 1);
solve(vc2, r - vc2.size() + 1, r);
}*/
/*
vector<int> Solve(int _n){
n = _n;
vector<int> temp;
for(int i = 0; i < n; i++) temp.pb(i);
solve(temp, 0, n - 1);
//solve_brute(temp, 0, n - 1);
vector<int> temp2;
for(int i = 0; i < n; i++) temp2.pb(a[i]);
return temp2;
}
void process(int t){
int n = 1000;
for(int i = 0; i < n; i++) b[i] = i;
shuffle(b, b + n, default_random_engine(rnd(1, 10000)));
cnt = 0;
//cout << "OK\n";
Solve(n);
cout << t << " " << cnt << "\n";
//for(int i = 0; i < n; i++) cout << a[i] << " " << b[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
for(int i = 1; i <= t; i++){
mp.clear();
//cout << i << "\n";
process(i);
}
//cout << fixed << setprecision(10) << (double)cnt / (double)t << "\n";
}*/
Compilation message
monster.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
monster.cpp:32:5: error: ambiguating new declaration of 'int Query(int, int)'
32 | int Query(int x, int y){
| ^~~~~
In file included from monster.cpp:1:
monster.h:4:6: note: old declaration 'bool Query(int, int)'
4 | bool Query(int a, int b);
| ^~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from monster.cpp:2:
monster.cpp: In function 'void solve_brute(std::vector<int>, int, int)':
monster.cpp:64:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
64 | assert(x.size() == (r - l + 1));
| ~~~~~~~~~^~~~~~~~~~~~~~
monster.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 0; i < x.size(); i++) deg[x[i]] = 0;
| ~~^~~~~~~~~~
monster.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i < x.size(); i++){
| ~~^~~~~~~~~~
monster.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j = i + 1; j < x.size(); j++){
| ~~^~~~~~~~~~
monster.cpp:73:4: error: 'Querry' was not declared in this scope; did you mean 'Query'?
73 | Querry(x[i], x[j]);
| ^~~~~~
| Query
monster.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(deg[it] >= 2 && deg[it] <= x.size() - 3){
| ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp:98:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | if(deg[it] == x.size() - 2){
| ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp: In function 'int med(int, int, int)':
monster.cpp:128:5: error: 'Querry' was not declared in this scope; did you mean 'Query'?
128 | if(Querry(a, b)) cnt[0]++; else cnt[1]++;
| ^~~~~~
| Query
monster.cpp:129:5: error: 'Querry' was not declared in this scope; did you mean 'Query'?
129 | if(Querry(a, c)) cnt[0]++; else cnt[2]++;
| ^~~~~~
| Query
monster.cpp:131:5: error: 'Querry' was not declared in this scope; did you mean 'Query'?
131 | if(Querry(b, c)) cnt[1]++; else cnt[2]++;
| ^~~~~~
| Query
monster.cpp: In function 'void solve(std::vector<int>, int, int)':
monster.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(int i = 0; i < can.size(); i += 3){
| ~~^~~~~~~~~~~~
monster.cpp:196:6: error: 'Querry' was not declared in this scope; did you mean 'Query'?
196 | if(Querry(it, w1)) w1 = it;
| ^~~~~~
| Query
monster.cpp:201:6: error: 'Querry' was not declared in this scope; did you mean 'Query'?
201 | if(Querry(w1, it)){
| ^~~~~~
| Query
monster.cpp:211:8: error: 'Querry' was not declared in this scope; did you mean 'Query'?
211 | w2 = (Querry(cans.fi, cans.se) ? cans.se : cans.fi);
| ^~~~~~
| Query
monster.cpp:144:6: warning: unused variable 'iter' [-Wunused-variable]
144 | int iter = 0;
| ^~~~
monster.cpp:212:7: warning: unused variable 'ck1' [-Wunused-variable]
212 | bool ck1 = 0, ck2 = 0;
| ^~~
monster.cpp:212:16: warning: unused variable 'ck2' [-Wunused-variable]
212 | bool ck1 = 0, ck2 = 0;
| ^~~
