#include "longesttrip.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace Query {
map<pii, bool> prec;
bool query(int a, int b) {
if(a > b) swap(a, b);
if(prec.count(pii{a, b})) return prec[pii{a, b}];
vector<int> t[2];
t[0].emplace_back(a);
t[1].emplace_back(b);
return prec[pii{a, b}] = are_connected(t[0], t[1]);
}
bool query(int a, vector<int> b) {
vector<int> t[2];
t[0].emplace_back(a);
t[1] = b;
return are_connected(t[0], t[1]);
}
bool query(vector<int> b, int a) {
return query(a, b);
}
bool query(vector<int> a, vector<int> b) {
return are_connected(a, b);
}
};
std::vector<int> longest_trip(int N, int D) {
Query::prec.clear();
using namespace Query;
vector<int> perm(N);
iota(all(perm), 0);
shuffle(all(perm), rng);
vector<int> st[2];
st[0].emplace_back(perm[0]);
bool certain = 0;
for(auto x : perm | views::drop(1)) {
if(sz(st[0]) < sz(st[1])) swap(st[0], st[1]);
if(sz(st[0]) && sz(st[1]) && rng() % 2 == 0) swap(st[0], st[1]);
//cerr << certain << '\t' << st[0].back() << ' ' << (sz(st[1])? st[1].back() : -1) << ' ' << x << '\n';
if(sz(st[1]) == 0) st[1].emplace_back(x);
else if(query(st[0].back(), x)) st[0].emplace_back(x), certain = 0;
else {
if(certain) st[1].emplace_back(x), certain = 0;
else {
if(query(st[1].back(), x))
st[1].emplace_back(x), certain = 1;
else {
copy(rbegin(st[1]), rend(st[1]), back_inserter(st[0]));
st[1].clear();
if(query(st[0].back(), x)) st[0].emplace_back(x);
else certain = 1, st[1].emplace_back(x);
}
}
}
}
if(sz(st[1]) == 0) return st[0];
if(sz(st[0]) == 0) return st[1]; // ???
if(rng() % 2 == 0) swap(st[0], st[1]); // nu o sa aibe niciun efect lol
//for(int i = 1; i < sz(st[0]); i++) assert(query(st[0][i], st[0][i - 1]));
//for(int i = 1; i < sz(st[1]); i++) assert(query(st[1][i], st[1][i - 1]));
//for(auto a : st[0]) cerr << a << ' '; cerr << '\n';
//for(auto a : st[1]) cerr << a << ' '; cerr << '\n';
if(query(st[0][0], st[1])) {
if(query(st[0][0], st[1].back()));
else if(query(st[0][0], st[1][0])) { reverse(all(st[1])); }
else {
int lim = 1;
for(int i = 10; i >= 0; i--) {
int cand = lim + (1 << i);
if(cand >= sz(st[1]) - 1) continue; // scoate -1ul ffs
if(!query(st[0][0], vector<int>(begin(st[1]), begin(st[1]) + cand))) lim = cand;
}
for(int i = 0; i < lim; i++) st[1].emplace_back(st[1][i]);
st[1].erase(begin(st[1]), begin(st[1]) + lim);
reverse(all(st[1]));
}
copy(all(st[0]), back_inserter(st[1]));
return st[1];
}
else {
if(!query(st[0], st[1])) return sz(st[0]) > sz(st[1])? st[0] : st[1];
int lim = 0;
for(int i = 10; i >= 0; i--) {
int cand = lim + (1 << i);
if(cand >= sz(st[1])) continue;
if(query(st[0], vector<int>(begin(st[1]) + cand, end(st[1])))) lim = cand;
}
swap(st[1][0], st[1][lim]);
if(query(st[0].back(), st[1][0]));
else {
lim = 1;
for(int i = 10; i >= 0; i--) {
int cand = lim + (1 << i);
if(cand >= sz(st[0]) - 1) continue; // scoate -1ul ffs
if(!query(st[1][0], vector<int>(begin(st[0]), begin(st[0]) + cand))) lim = cand;
}
for(int i = 0; i < lim; i++) st[0].emplace_back(st[0][i]);
st[0].erase(begin(st[0]), begin(st[0]) + lim);
reverse(all(st[0]));
}
copy(all(st[1]), back_inserter(st[0]));
return st[0];
}
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:53:24: error: 'views' has not been declared
53 | for(auto x : perm | views::drop(1)) {
| ^~~~~
