| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 476930 | leaked | Mouse (info1cup19_mouse) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "grader.h"
//#include "grader.cpp"
#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef pair<int,int> pii;
typedef long double ld;
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
typedef long long ll;
const ll inf=1e18+100;
//const int N=49;
int query(vector<int> q);
int mx=0;
int tests=1000;
void solve(int n){
/// let's try
tests--;
vec<int>pr(n);iota(all(pr),1);
int cnt=(n>50?2398:n>7?398:49);cnt--;
// vec<vec<ll>>answ(n,vec<ll>(n+1,0));
// vec<vec<int>>cntt(n,vec<int>(n+1,0));
// vec<int>how(n,n);
// vec<int>p(n)
map<vec<int>,int>gp;
tt=0;
while(1){
int how=query(pr);
if(how==n) return;
cnt--;
if(how==0){
if(tt==1) break;
tt++;
}
random_shuffle(all(pr));
}
auto del=[&](vec<int> &x,int v){
int j=lower_bound(all(x),v)-x.begin();
x.erase(x.begin()+j,x.begin()+j+1);
};
vec<vec<bool>>used(n,vec<bool>(n+1,0));
if(n<=256){
vec<int>badp;
vec<int>bad;
for(int i=1;i<=n;i++) bad.pb(i),badp.pb(i-1);
int pv=0;
for(int i=0;i<n;i++){
while(binary_search(all(badp),i)){
int j=rng()%sz(bad);
j=bad[j];
if(used[i][j]) continue;
int t=-1;
for(int k=0;k<n;k++){
if(pr[k]==j) t=k;
}
if(i==t || !binary_search(all(badp),t)) continue;
used[i][j]=1;
used[t][pr[i]]=1;
swap(pr[i],pr[t]);
// debug()<<imie("TRY ")imie(pr)imie(x);
int x=query(pr);
// debug()<<imie("TRY ")imie(x);
// if(t==5){
// t=5;
// }
if(x==n) return;
if(x>pv){
if(x==pv+2){
del(badp,i);del(badp,t);
del(bad,pr[i]);del(bad,pr[t]);
}
else{
// debug()<<imie("OD")imie(pr)imie(x);
int yself=-1;
for(auto &z : badp)if(z!=i && z!=t){yself=z;break;}
swap(pr[i],pr[yself]);
int y=query(pr);
if(y==n) return;
// if(y==pv+2){
// del(badp,yself);del(badp,t);
// del(bad,pr[yself]);del(bad,pr[t]);
// x=y;
// continue;
// }
// debug()<<imie(pr)imie(y);
// system("pause");
swap(pr[i],pr[yself]);
if(y!=pv){
del(badp,t);del(bad,pr[t]);
}
else{
del(badp,i);del(bad,pr[i]);
}
}
pv=x;
// debug()<<imie("NEW")imie(pr);
continue;
}
swap(pr[i],pr[t]);
}
}
assert(pv==n);
return;
}
// vec<int>bad;
// for(int i=1;i<=n;i++) bad.pb(i);
// int x=0;
// while(x!=n){
//// cout<<"ASK"<<endl;
// int i=rng()%n,j=rng()%sz(bad);
// for(int t=0;t<n;t++){
//
// }
// swap(pr[i],pr[j]);
// int y=query(pr);
// if(y==n) break;
// if(y>x) continue;
// else swap(pr[i],pr[j]);
// }
query(pr);
return ;
}