# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
477024 |
2021-09-29T20:09:51 Z |
leaked |
Mouse (info1cup19_mouse) |
C++14 |
|
89 ms |
292 KB |
#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);
while(1){
int how=query(pr);
if(how==n) return;
if(how==0) break;
random_shuffle(all(pr));
}
vec<vec<pii>>w(n,vec<pii>());
auto del=[&](vec<int> &x,int v){
int j=find(all(x),v)-x.begin();
x.erase(x.begin()+j,x.begin()+j+1);
};
vec<int>badp,bad;
for(int i=1;i<=n;i++) bad.pb(i),badp.pb(i-1);
int pv=0;
while(1){
random_shuffle(all(badp));
int whatt=0;
for(int j=0;2*j+1<sz(badp);j++)swap(pr[badp[2*j]],pr[badp[2*j+1]]);
whatt=query(pr);
for(int j=0;2*j+1<sz(badp);j++)swap(pr[badp[2*j]],pr[badp[2*j+1]]);
if(whatt==pv) continue;
if(whatt==n) return;
int l=0,r=sz(badp)/2;
// debug()<<imie(sz(badp));
int mem=-1;
while(l!=r){
int tm=(l+r)>>1;
for(int j=0;j<=tm;j++) swap(pr[badp[2*j]],pr[badp[2*j+1]]);
int x=query(pr);
if(x==n) return;
for(int j=0;j<=tm;j++) swap(pr[badp[2*j]],pr[badp[2*j+1]]);
if(x>pv) r=tm,mem=x;
else l=tm+1;
}
// if(r==sz(badp)/2){
// continue;
// }
int v=badp[2*l],u=badp[2*l+1];
swap(pr[v],pr[u]);
int x=query(pr);
if(x==pv+2){
del(badp,v);del(badp,u);
del(bad,pr[v]);del(bad,pr[u]);
}
else{
int yself=-1;
for(auto &z : badp)if(z!=v && z!=u){yself=z;break;}
swap(pr[v],pr[yself]);
int y=query(pr);
if(y==n) return;
swap(pr[v],pr[yself]);
if(y!=pv){
del(badp,u);del(bad,pr[u]);
}
else{
del(badp,v);del(bad,pr[v]);
}
}
pv=x;
// debug()<<imie(pr);
continue;
}
query(pr);
return ;
}
Compilation message
mouse.cpp: In function 'void solve(int)':
mouse.cpp:78:13: warning: variable 'mem' set but not used [-Wunused-but-set-variable]
78 | int mem=-1;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 26 |
2 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 10 |
3 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 27 |
4 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 28 |
5 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 14 |
6 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 26 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 26 |
2 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 10 |
3 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 27 |
4 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 28 |
5 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 14 |
6 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 26 |
7 |
Correct |
4 ms |
200 KB |
Correct! Number of queries: 400 |
8 |
Correct |
7 ms |
200 KB |
Correct! Number of queries: 400 |
9 |
Correct |
6 ms |
200 KB |
Correct! Number of queries: 400 |
10 |
Correct |
7 ms |
200 KB |
Correct! Number of queries: 400 |
11 |
Correct |
5 ms |
200 KB |
Correct! Number of queries: 300 |
12 |
Correct |
7 ms |
200 KB |
Correct! Number of queries: 400 |
13 |
Correct |
6 ms |
200 KB |
Correct! Number of queries: 400 |
14 |
Correct |
5 ms |
200 KB |
Correct! Number of queries: 400 |
15 |
Correct |
5 ms |
200 KB |
Correct! Number of queries: 400 |
16 |
Correct |
3 ms |
292 KB |
Correct! Number of queries: 400 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 26 |
2 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 10 |
3 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 27 |
4 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 28 |
5 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 14 |
6 |
Correct |
1 ms |
200 KB |
Correct! Number of queries: 26 |
7 |
Correct |
4 ms |
200 KB |
Correct! Number of queries: 400 |
8 |
Correct |
7 ms |
200 KB |
Correct! Number of queries: 400 |
9 |
Correct |
6 ms |
200 KB |
Correct! Number of queries: 400 |
10 |
Correct |
7 ms |
200 KB |
Correct! Number of queries: 400 |
11 |
Correct |
5 ms |
200 KB |
Correct! Number of queries: 300 |
12 |
Correct |
7 ms |
200 KB |
Correct! Number of queries: 400 |
13 |
Correct |
6 ms |
200 KB |
Correct! Number of queries: 400 |
14 |
Correct |
5 ms |
200 KB |
Correct! Number of queries: 400 |
15 |
Correct |
5 ms |
200 KB |
Correct! Number of queries: 400 |
16 |
Correct |
3 ms |
292 KB |
Correct! Number of queries: 400 |
17 |
Correct |
75 ms |
200 KB |
Correct! Number of queries: 2400 |
18 |
Correct |
77 ms |
200 KB |
Correct! Number of queries: 2300 |
19 |
Correct |
77 ms |
200 KB |
Correct! Number of queries: 2300 |
20 |
Correct |
89 ms |
200 KB |
Correct! Number of queries: 2400 |
21 |
Correct |
84 ms |
200 KB |
Correct! Number of queries: 2300 |
22 |
Correct |
84 ms |
200 KB |
Correct! Number of queries: 2300 |
23 |
Correct |
84 ms |
200 KB |
Correct! Number of queries: 2300 |
24 |
Correct |
84 ms |
200 KB |
Correct! Number of queries: 2400 |
25 |
Correct |
82 ms |
200 KB |
Correct! Number of queries: 2400 |
26 |
Correct |
87 ms |
200 KB |
Correct! Number of queries: 2400 |