#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;
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){
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";
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;
}
}
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;
vector<int> vc1, vc2;
int iter = 0;
temp = x[rnd(0, x.size() - 1)];
int cnt1 = 0, cnt2 = 0;
vector<int> sm, la;
for(int i = 0; (sm.size() + la.size()) < 10; i++){
if(temp == x[i]) continue;
if(Querry(temp, x[i])) sm.pb(x[i]);
else la.pb(x[i]);
}
if(sm.size() < 2){
for(auto it : la){
int cnt = 0;
for(auto it2 : la) if(it != it2 && Querry(it, it2)) cnt++;
if(cnt >= 2 && cnt <= 6){
temp = it;
break;
}
}
}
if(la.size() < 2){
for(auto it : sm){
int cnt = 0;
for(auto it2 : sm) if(it != it2 && Querry(it, it2)) cnt++;
if(cnt >= 3 && cnt <= 7){
temp = it;
break;
}
}
}
//cout << l << " " << r << " " << temp << "\n";
//if(cnt1 < 2 || cnt2 < 2) continue;
//break;
//cout << temp << "\n";
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;
}
for(auto it : vc2){
if(it == w2) continue;
if(Querry(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);
//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;
assert(n == 1000);
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);
if(cnt >= 18000) 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;
| ~~~~~^~~
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:61:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
61 | assert(x.size() == (r - l + 1));
| ~~~~~~~~~^~~~~~~~~~~~~~
monster.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < x.size(); i++) deg[x[i]] = 0;
| ~~^~~~~~~~~~
monster.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < x.size(); i++){
| ~~^~~~~~~~~~
monster.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int j = i + 1; j < x.size(); j++){
| ~~^~~~~~~~~~
monster.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | if(deg[it] >= 2 && deg[it] <= x.size() - 3){
| ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp:95:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if(deg[it] == x.size() - 2){
| ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp: In function 'void solve(std::vector<int>, int, int)':
monster.cpp:131:6: warning: unused variable 'iter' [-Wunused-variable]
131 | int iter = 0;
| ^~~~
monster.cpp:133:6: warning: unused variable 'cnt1' [-Wunused-variable]
133 | int cnt1 = 0, cnt2 = 0;
| ^~~~
monster.cpp:133:16: warning: unused variable 'cnt2' [-Wunused-variable]
133 | int cnt1 = 0, cnt2 = 0;
| ^~~~
monster.cpp:181:7: warning: unused variable 'ck1' [-Wunused-variable]
181 | bool ck1 = 0, ck2 = 0;
| ^~~
monster.cpp:181:16: warning: unused variable 'ck2' [-Wunused-variable]
181 | bool ck1 = 0, ck2 = 0;
| ^~~
monster.cpp: In function 'void solve_brute(std::vector<int>, int, int)':
monster.cpp:108:22: warning: 'mn1' may be used uninitialized in this function [-Wmaybe-uninitialized]
108 | a[mn0] = l; a[mn1] = l + 1;
| ~~~~~~~^~~~~~~
monster.cpp:85:31: warning: 'mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
85 | int mn0 = -1, mn1, mx0 = -1, mx1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
