oj.uz

Submission #477023

# Submission time Handle Problem Language Result Execution time Memory
477023 2021-09-29T20:07:25 Z leaked Mouse (info1cup19_mouse) C++14
100 / 100
 111 ms 296 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=mem;
        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 ;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 21
2 Correct 1 ms 200 KB Correct! Number of queries: 8
3 Correct 1 ms 200 KB Correct! Number of queries: 23
4 Correct 1 ms 200 KB Correct! Number of queries: 23
5 Correct 1 ms 200 KB Correct! Number of queries: 12
6 Correct 1 ms 200 KB Correct! Number of queries: 23

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 21
2 Correct 1 ms 200 KB Correct! Number of queries: 8
3 Correct 1 ms 200 KB Correct! Number of queries: 23
4 Correct 1 ms 200 KB Correct! Number of queries: 23
5 Correct 1 ms 200 KB Correct! Number of queries: 12
6 Correct 1 ms 200 KB Correct! Number of queries: 23
7 Correct 4 ms 200 KB Correct! Number of queries: 300
8 Correct 7 ms 200 KB Correct! Number of queries: 400
9 Correct 4 ms 200 KB Correct! Number of queries: 300
10 Correct 9 ms 200 KB Correct! Number of queries: 400
11 Correct 5 ms 200 KB Correct! Number of queries: 300
12 Correct 6 ms 200 KB Correct! Number of queries: 400
13 Correct 8 ms 200 KB Correct! Number of queries: 300
14 Correct 6 ms 200 KB Correct! Number of queries: 300
15 Correct 8 ms 200 KB Correct! Number of queries: 300
16 Correct 5 ms 200 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: 21
2 Correct 1 ms 200 KB Correct! Number of queries: 8
3 Correct 1 ms 200 KB Correct! Number of queries: 23
4 Correct 1 ms 200 KB Correct! Number of queries: 23
5 Correct 1 ms 200 KB Correct! Number of queries: 12
6 Correct 1 ms 200 KB Correct! Number of queries: 23
7 Correct 4 ms 200 KB Correct! Number of queries: 300
8 Correct 7 ms 200 KB Correct! Number of queries: 400
9 Correct 4 ms 200 KB Correct! Number of queries: 300
10 Correct 9 ms 200 KB Correct! Number of queries: 400
11 Correct 5 ms 200 KB Correct! Number of queries: 300
12 Correct 6 ms 200 KB Correct! Number of queries: 400
13 Correct 8 ms 200 KB Correct! Number of queries: 300
14 Correct 6 ms 200 KB Correct! Number of queries: 300
15 Correct 8 ms 200 KB Correct! Number of queries: 300
16 Correct 5 ms 200 KB Correct! Number of queries: 400
17 Correct 110 ms 200 KB Correct! Number of queries: 2200
18 Correct 82 ms 200 KB Correct! Number of queries: 2000
19 Correct 83 ms 200 KB Correct! Number of queries: 2000
20 Correct 92 ms 200 KB Correct! Number of queries: 2200
21 Correct 58 ms 200 KB Correct! Number of queries: 2100
22 Correct 75 ms 200 KB Correct! Number of queries: 2000
23 Correct 67 ms 200 KB Correct! Number of queries: 2100
24 Correct 96 ms 296 KB Correct! Number of queries: 2200
25 Correct 78 ms 296 KB Correct! Number of queries: 2100
26 Correct 111 ms 200 KB Correct! Number of queries: 2200