oj.uz

답안 #930862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930862 2024-02-20T14:21:45 Z Tuanlinh123 Mouse (info1cup19_mouse) C++17
45 / 100
 3000 ms 800 KB 
#include "grader.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(ll n) 
{
    ll q=n>50?2999:n>7?499:49, turn=-1, answered=0;
    vector <ll> crr(n);
    vector <vector <ll>> p(n+1, vector <ll> (n+1, 1));
    auto ask=[&](vector <ll> a, bool track)
    {
        if (answered) return n;
        if (track)
        {
            ll cnt=0;
            for (ll j=0; j<n; j++)
                cnt+=p[j+1][crr[j]];
            if (!cnt) {turn--; return 0;}
        }
        ll q=query(a);
        if (q==n) answered=1;
        return q;
    };
    while (turn+1<q)
    {
        turn++;
        if (turn%n==0)
        {
            iota(crr.begin(), crr.end(), 1);
            shuffle(crr.begin(), crr.end(), rng);
        }
        else rotate(crr.begin(), crr.begin()+1, crr.end());
        if (!ask(crr, 1)) for (ll j=0; j<n; j++) p[j+1][crr[j]]=0;
    }
    vector <ll> ans(n, 0), deg(n+1, 0);
    for (ll i=1; i<=n; i++)
        for (ll j=1; j<=n; j++)
            deg[i]+=p[i][j];
    function<void(ll)> backtrack=[&](ll id)
    {
        if (id==n) {ask(ans, 0); return;}
        pll best={n, 0};
        for (ll i=1; i<=n; i++)
            if (deg[i]>0) best=min(best, {deg[i], i});
        if (best.se==0) return;
        ll c=best.se; deg[c]=0;
        for (ll i=1; i<=n; i++)
        {
            if (!p[c][i]) continue;
            vector <ll> er;
            for (ll j=1; j<=n; j++)
                if (p[j][i]) p[j][i]=0, deg[j]--, er.pb(j);
            ans[c-1]=i, backtrack(id+1);
            for (ll j:er) p[j][i]=1, deg[j]++;
        }
        deg[c]=best.fi;
    }; backtrack(0);
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 50
2 Correct 0 ms 344 KB Correct! Number of queries: 50
3 Correct 0 ms 344 KB Correct! Number of queries: 50
4 Correct 0 ms 344 KB Correct! Number of queries: 50
5 Correct 0 ms 344 KB Correct! Number of queries: 50
6 Correct 1 ms 344 KB Correct! Number of queries: 50

Subtask #2
31.99999 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 50
2 Correct 0 ms 344 KB Correct! Number of queries: 50
3 Correct 0 ms 344 KB Correct! Number of queries: 50
4 Correct 0 ms 344 KB Correct! Number of queries: 50
5 Correct 0 ms 344 KB Correct! Number of queries: 50
6 Correct 1 ms 344 KB Correct! Number of queries: 50
7 Correct 4 ms 452 KB Correct! Number of queries: 600
8 Correct 4 ms 452 KB Correct! Number of queries: 600
9 Correct 4 ms 452 KB Correct! Number of queries: 600
10 Correct 4 ms 448 KB Correct! Number of queries: 600
11 Correct 3 ms 444 KB Correct! Number of queries: 600
12 Correct 4 ms 456 KB Correct! Number of queries: 600
13 Correct 3 ms 452 KB Correct! Number of queries: 600
14 Correct 4 ms 452 KB Correct! Number of queries: 600
15 Correct 4 ms 452 KB Correct! Number of queries: 600
16 Correct 4 ms 452 KB Correct! Number of queries: 600

Subtask #3
0.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 50
2 Correct 0 ms 344 KB Correct! Number of queries: 50
3 Correct 0 ms 344 KB Correct! Number of queries: 50
4 Correct 0 ms 344 KB Correct! Number of queries: 50
5 Correct 0 ms 344 KB Correct! Number of queries: 50
6 Correct 1 ms 344 KB Correct! Number of queries: 50
7 Correct 4 ms 452 KB Correct! Number of queries: 600
8 Correct 4 ms 452 KB Correct! Number of queries: 600
9 Correct 4 ms 452 KB Correct! Number of queries: 600
10 Correct 4 ms 448 KB Correct! Number of queries: 600
11 Correct 3 ms 444 KB Correct! Number of queries: 600
12 Correct 4 ms 456 KB Correct! Number of queries: 600
13 Correct 3 ms 452 KB Correct! Number of queries: 600
14 Correct 4 ms 452 KB Correct! Number of queries: 600
15 Correct 4 ms 452 KB Correct! Number of queries: 600
16 Correct 4 ms 452 KB Correct! Number of queries: 600
17 Correct 70 ms 692 KB Correct! Number of queries: 3100
18 Correct 61 ms 800 KB Correct! Number of queries: 3100
19 Correct 61 ms 664 KB Correct! Number of queries: 3100
20 Correct 69 ms 684 KB Correct! Number of queries: 3100
21 Correct 62 ms 672 KB Correct! Number of queries: 3100
22 Correct 61 ms 672 KB Correct! Number of queries: 3100
23 Correct 63 ms 664 KB Correct! Number of queries: 3100
24 Execution timed out 3040 ms 692 KB Time limit exceeded
25 Halted 0 ms 0 KB -