oj.uz

Submission #477024

# Submission time Handle Problem Language Result Execution time Memory
477024 2021-09-29T20:09:51 Z leaked Mouse (info1cup19_mouse) C++14
100 / 100
 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;
      |             ^~~

Subtask #1
13.0 / 13.0

# 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

Subtask #2
38.0 / 38.0

# 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

Subtask #3
49.0 / 49.0

# 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