oj.uz

답안 #398555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398555 2021-05-04T13:59:27 Z MarcoMeijer Mouse (info1cup19_mouse) C++14
27.2644 / 100
 206 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}

 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<20);

int query(vi q);

int findFirst(int n) {
    vi perm;
    RE1(i,n) perm.pb(i);

    bool first = true;
    vi possible;

    while(true) {
        int res = query(perm);
        if(res == n) return -1;

        int bestRes = 0;
        REP(i,1,n) {
            swap(perm[0], perm[i]);
            int nRes = query(perm);
            if(nRes == n) return -1;
            bestRes = max(bestRes, nRes);
            if(nRes == res + 2) return perm[0];
            if(first && nRes == res + 1) possible.pb(perm[0]);
            swap(perm[0], perm[i]);
        }

        if(bestRes == res - 1) return perm[0];

        first = false;
        perm.clear();
        perm.pb(possible.back());
        RE1(i,n) if(i != possible.back()) perm.pb(i);
        possible.pop_back();
    }
}

void solve(int n) {
    int first = findFirst(n);
    if(first == -1) return;

    vi ans; ans.assign(n,0);
    ans[0] = first;

    vi perm;
    perm.pb(first);
    RE1(i,n) if(i != first) perm.pb(i);

    RE(_,n) {
        int res = query(perm);
        if(res == n) return;

        REP(i,1,n) {
            swap(perm[0],perm[i]);
            int nRes = query(perm);
            if(nRes == n) return;
            if(nRes == res - 2) ans[i] = perm[0];
            swap(perm[0],perm[i]);
        }

        // cycle permutation
        int temp = perm[1];
        REP(i,1,n-1) perm[i] = perm[i+1];
        perm[n-1] = temp;
    }

    query(ans);
}

#ifdef debug
int n;
vi ans;

int query(vi q) {
    int res = 0;
    RE(i,n) if(ans[i] == q[i]) res++;
    if(res == n) OUTL("Correct!");
    return res;
}

int main() {
    IN(n); ans.assign(n,0);
    RE(i,n) IN(ans[i]);
    solve(n);
}
#endif

Subtask #1
9.000004 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Correct! Number of queries: 64
2 Correct 1 ms 200 KB Correct! Number of queries: 29
3 Correct 1 ms 200 KB Correct! Number of queries: 55
4 Correct 1 ms 200 KB Correct! Number of queries: 71
5 Correct 2 ms 204 KB Correct! Number of queries: 64
6 Correct 1 ms 200 KB Correct! Number of queries: 57

Subtask #2
18.264358 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Correct! Number of queries: 64
2 Correct 1 ms 200 KB Correct! Number of queries: 29
3 Correct 1 ms 200 KB Correct! Number of queries: 55
4 Correct 1 ms 200 KB Correct! Number of queries: 71
5 Correct 2 ms 204 KB Correct! Number of queries: 64
6 Correct 1 ms 200 KB Correct! Number of queries: 57
7 Correct 51 ms 200 KB Correct! Number of queries: 2700
8 Correct 50 ms 200 KB Correct! Number of queries: 2700
9 Correct 44 ms 200 KB Correct! Number of queries: 2300
10 Correct 63 ms 200 KB Correct! Number of queries: 2700
11 Correct 29 ms 200 KB Correct! Number of queries: 1900
12 Correct 35 ms 200 KB Correct! Number of queries: 2600
13 Correct 37 ms 200 KB Correct! Number of queries: 2300
14 Correct 53 ms 200 KB Correct! Number of queries: 2700
15 Correct 45 ms 204 KB Correct! Number of queries: 2700
16 Correct 46 ms 200 KB Correct! Number of queries: 2700

Subtask #3
0.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 200 KB Correct! Number of queries: 64
2 Correct 1 ms 200 KB Correct! Number of queries: 29
3 Correct 1 ms 200 KB Correct! Number of queries: 55
4 Correct 1 ms 200 KB Correct! Number of queries: 71
5 Correct 2 ms 204 KB Correct! Number of queries: 64
6 Correct 1 ms 200 KB Correct! Number of queries: 57
7 Correct 51 ms 200 KB Correct! Number of queries: 2700
8 Correct 50 ms 200 KB Correct! Number of queries: 2700
9 Correct 44 ms 200 KB Correct! Number of queries: 2300
10 Correct 63 ms 200 KB Correct! Number of queries: 2700
11 Correct 29 ms 200 KB Correct! Number of queries: 1900
12 Correct 35 ms 200 KB Correct! Number of queries: 2600
13 Correct 37 ms 200 KB Correct! Number of queries: 2300
14 Correct 53 ms 200 KB Correct! Number of queries: 2700
15 Correct 45 ms 204 KB Correct! Number of queries: 2700
16 Correct 46 ms 200 KB Correct! Number of queries: 2700
17 Runtime error 206 ms 200 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -