제출 #398555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398555		MarcoMeijer	Mouse (info1cup19_mouse)	C++14	27.26 / 100	206 ms	204 KiB

mouse

#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
• Subtask 2: 18.264357999999998 / 38
• Subtask 3: 0 / 49