//#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++;
if(b[x] < (b[y] - 1)) return 0;
if(b[x] == (b[y] + 1)) return 0;
return 1;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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];
map<ii, bool> mp;
void solve_brute(vector<int> x, int l, int r){
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++){
for(int j = i + 1; j < x.size(); j++){
mp[{x[i], x[j]}] = Query(x[i], x[j]);
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;
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;
}
}
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;
}
}
void solve(vector<int> x, int l, int r){
if(x.size() <= 10){
//solve_brute(x, l, r);
return;
}
int temp;
vector<int> vc1, vc2;
int iter = 0;
while(1){
iter++;
temp = x[rnd(0, x.size() - 1)];
int cnt1 = 0, cnt2 = 0;
for(int i = 0; (cnt1 + cnt2) < 10; i++){
if(temp == x[i]) continue;
if(Query(temp, x[i])) cnt1++;
else cnt2++;
}
if(cnt1 < 3 || cnt2 < 3) continue;
break;
}
for(auto it : x){
if(it == temp) continue;
if(Query(temp, it)) vc1.pb(it);
else vc2.pb(it);
}
//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 n = 1000;
for(int i = 1; i <= n; i++) b[i] = i;
shuffle(b + 1, b + n + 1, default_random_engine(rnd(1, 10000)));
cnt = 0;
Solve(n);
cout << cnt << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--) process();
}
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;
| ~~~~~^~~
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:51:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
51 | assert(x.size() == (r - l + 1));
| ~~~~~~~~~^~~~~~~~~~~~~~
monster.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < x.size(); i++){
| ~~^~~~~~~~~~
monster.cpp:58:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j = i + 1; j < x.size(); j++){
| ~~^~~~~~~~~~
monster.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if(deg[it] >= 2 && deg[it] <= x.size() - 3){
| ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp:82:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(deg[it] == x.size() - 2){
| ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp: In function 'void solve(std::vector<int>, int, int)':
monster.cpp:137:7: warning: unused variable 'ck1' [-Wunused-variable]
137 | bool ck1 = 0, ck2 = 0;
| ^~~
monster.cpp:137:16: warning: unused variable 'ck2' [-Wunused-variable]
137 | bool ck1 = 0, ck2 = 0;
| ^~~
monster.cpp: In function 'void solve_brute(std::vector<int>, int, int)':
monster.cpp:97:22: warning: 'mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
97 | a[mx0] = r; a[mx1] = r - 1;
| ~~~~~~~^~~~~~~
monster.cpp:88:22: warning: 'mn1' may be used uninitialized in this function [-Wmaybe-uninitialized]
88 | a[mn0] = l; a[mn1] = l + 1;
| ~~~~~~~^~~~~~~
/usr/bin/ld: /tmp/cckKMMUT.o: in function `Query(int, int)':
stub.cpp:(.text+0x0): multiple definition of `Query(int, int)'; /tmp/ccov4ybU.o:monster.cpp:(.text+0x1d0): first defined here
/usr/bin/ld: /tmp/cckKMMUT.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccov4ybU.o:monster.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
