oj.uz

Submission #930863

# Submission time Handle Problem Language Result Execution time Memory
930863 2024-02-20T14:23:30 Z Tuanlinh123 Mouse (info1cup19_mouse) C++17
90.8462 / 100
 372 ms 700 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?3050:n>7?450: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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 50
2 Correct 0 ms 344 KB Correct! Number of queries: 5
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 0 ms 344 KB Correct! Number of queries: 50

Subtask #2
35.000014 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 50
2 Correct 0 ms 344 KB Correct! Number of queries: 5
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 0 ms 344 KB Correct! Number of queries: 50
7 Correct 3 ms 456 KB Correct! Number of queries: 500
8 Correct 3 ms 456 KB Correct! Number of queries: 500
9 Correct 3 ms 452 KB Correct! Number of queries: 500
10 Correct 3 ms 452 KB Correct! Number of queries: 500
11 Correct 4 ms 344 KB Correct! Number of queries: 500
12 Correct 3 ms 456 KB Correct! Number of queries: 500
13 Correct 3 ms 448 KB Correct! Number of queries: 500
14 Correct 3 ms 452 KB Correct! Number of queries: 500
15 Correct 4 ms 452 KB Correct! Number of queries: 500
16 Correct 3 ms 452 KB Correct! Number of queries: 500

Subtask #3
42.846139 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 50
2 Correct 0 ms 344 KB Correct! Number of queries: 5
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 0 ms 344 KB Correct! Number of queries: 50
7 Correct 3 ms 456 KB Correct! Number of queries: 500
8 Correct 3 ms 456 KB Correct! Number of queries: 500
9 Correct 3 ms 452 KB Correct! Number of queries: 500
10 Correct 3 ms 452 KB Correct! Number of queries: 500
11 Correct 4 ms 344 KB Correct! Number of queries: 500
12 Correct 3 ms 456 KB Correct! Number of queries: 500
13 Correct 3 ms 448 KB Correct! Number of queries: 500
14 Correct 3 ms 452 KB Correct! Number of queries: 500
15 Correct 4 ms 452 KB Correct! Number of queries: 500
16 Correct 3 ms 452 KB Correct! Number of queries: 500
17 Correct 65 ms 684 KB Correct! Number of queries: 3100
18 Correct 62 ms 664 KB Correct! Number of queries: 3100
19 Correct 62 ms 668 KB Correct! Number of queries: 3100
20 Correct 242 ms 688 KB Correct! Number of queries: 3200
21 Correct 62 ms 688 KB Correct! Number of queries: 3100
22 Correct 61 ms 672 KB Correct! Number of queries: 3100
23 Correct 64 ms 668 KB Correct! Number of queries: 3100
24 Correct 372 ms 700 KB Correct! Number of queries: 3100
25 Correct 65 ms 684 KB Correct! Number of queries: 3100
26 Correct 64 ms 688 KB Correct! Number of queries: 3100