oj.uz

답안 #477020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477020 2021-09-29T19:54:39 Z leaked Mouse (info1cup19_mouse) C++14
96.1538 / 100
 114 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 l=0,r=sz(badp)/2;
        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;
            else l=tm+1;
        }
//        debug()<<imie(badp);
        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){
            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;
        }
        if(pv==n) return;
    }

    query(pr);
    return ;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 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: 25
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 256 KB Correct! Number of queries: 23

Subtask #2
38.0 / 38.0

# 결과 실행 시간 메모리 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: 25
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 256 KB Correct! Number of queries: 23
7 Correct 5 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 6 ms 200 KB Correct! Number of queries: 400
11 Correct 6 ms 200 KB Correct! Number of queries: 400
12 Correct 7 ms 200 KB Correct! Number of queries: 400
13 Correct 7 ms 200 KB Correct! Number of queries: 400
14 Correct 6 ms 200 KB Correct! Number of queries: 400
15 Correct 6 ms 200 KB Correct! Number of queries: 400
16 Correct 5 ms 292 KB Correct! Number of queries: 400

Subtask #3
45.153843 / 49.0

# 결과 실행 시간 메모리 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: 25
5 Correct 1 ms 200 KB Correct! Number of queries: 15
6 Correct 1 ms 256 KB Correct! Number of queries: 23
7 Correct 5 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 6 ms 200 KB Correct! Number of queries: 400
11 Correct 6 ms 200 KB Correct! Number of queries: 400
12 Correct 7 ms 200 KB Correct! Number of queries: 400
13 Correct 7 ms 200 KB Correct! Number of queries: 400
14 Correct 6 ms 200 KB Correct! Number of queries: 400
15 Correct 6 ms 200 KB Correct! Number of queries: 400
16 Correct 5 ms 292 KB Correct! Number of queries: 400
17 Correct 94 ms 200 KB Correct! Number of queries: 2700
18 Correct 84 ms 200 KB Correct! Number of queries: 2400
19 Correct 88 ms 200 KB Correct! Number of queries: 2500
20 Correct 97 ms 200 KB Correct! Number of queries: 2800
21 Correct 98 ms 200 KB Correct! Number of queries: 2700
22 Correct 73 ms 200 KB Correct! Number of queries: 2600
23 Correct 97 ms 200 KB Correct! Number of queries: 2600
24 Correct 87 ms 200 KB Correct! Number of queries: 2800
25 Correct 93 ms 200 KB Correct! Number of queries: 2700
26 Correct 114 ms 200 KB Correct! Number of queries: 2900