oj.uz

Submission #930717

# Submission time Handle Problem Language Result Execution time Memory
930717 2024-02-20T09:59:24 Z Tuanlinh123 Mouse (info1cup19_mouse) C++17
39.3333 / 100
 123 ms 688 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=4000, cnt=-1;
    vector <vector <ll>> p(n+1, vector <ll> (n+1, 1));
    vector <ll> crr(n);
    while (1)
    {
        cnt++;
        if (cnt+1==q)
        {
            vector <ll> ans;
            vector <bool> check(n, 0);
            for (ll j=1; j<=n; j++)
                for (ll k=1; k<=n; k++)
                    if (p[j][k] && !check[k]) {ans.pb(k), check[k]=1; break;}
            query(ans); return;
        }
        if (cnt%n==0)
        {
            iota(crr.begin(), crr.end(), 1);
            shuffle(crr.begin(), crr.end(), rng);
        }
        else rotate(crr.begin(), crr.begin()+1, crr.end());
        ll cnt=0;
        for (ll j=0; j<n; j++)
            cnt+=p[j+1][crr[j]];
        if (!cnt) continue;
        ll q=query(crr);
        if (q==n) return;
        if (!q) 
        {
            for (ll j=0; j<n; j++)
                p[j+1][crr[j]]=0;
            bool ok=1;
            for (ll j=1; j<=n; j++)
            {
                ll cnt=0;
                for (ll k=1; k<=n; k++)
                    cnt+=p[j][k];
                if (cnt>1) ok=0;
            }
            if (ok)
            {
                vector <ll> ans;
                for (ll j=1; j<=n; j++)
                    for (ll k=1; k<=n; k++)
                        if (p[j][k]) {ans.pb(k); break;}
                query(ans); return;
            }
        }
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 43
2 Correct 0 ms 344 KB Correct! Number of queries: 16
3 Correct 0 ms 344 KB Correct! Number of queries: 37
4 Correct 0 ms 344 KB Correct! Number of queries: 41
5 Correct 0 ms 344 KB Correct! Number of queries: 46
6 Correct 1 ms 344 KB Correct! Number of queries: 41

Subtask #2
26.333316 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 43
2 Correct 0 ms 344 KB Correct! Number of queries: 16
3 Correct 0 ms 344 KB Correct! Number of queries: 37
4 Correct 0 ms 344 KB Correct! Number of queries: 41
5 Correct 0 ms 344 KB Correct! Number of queries: 46
6 Correct 1 ms 344 KB Correct! Number of queries: 41
7 Correct 6 ms 344 KB Correct! Number of queries: 900
8 Correct 6 ms 344 KB Correct! Number of queries: 800
9 Correct 5 ms 344 KB Correct! Number of queries: 800
10 Correct 5 ms 344 KB Correct! Number of queries: 800
11 Correct 4 ms 448 KB Correct! Number of queries: 600
12 Correct 5 ms 344 KB Correct! Number of queries: 700
13 Correct 5 ms 344 KB Correct! Number of queries: 700
14 Correct 5 ms 344 KB Correct! Number of queries: 700
15 Correct 5 ms 344 KB Correct! Number of queries: 800
16 Correct 4 ms 344 KB Correct! Number of queries: 600

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 43
2 Correct 0 ms 344 KB Correct! Number of queries: 16
3 Correct 0 ms 344 KB Correct! Number of queries: 37
4 Correct 0 ms 344 KB Correct! Number of queries: 41
5 Correct 0 ms 344 KB Correct! Number of queries: 46
6 Correct 1 ms 344 KB Correct! Number of queries: 41
7 Correct 6 ms 344 KB Correct! Number of queries: 900
8 Correct 6 ms 344 KB Correct! Number of queries: 800
9 Correct 5 ms 344 KB Correct! Number of queries: 800
10 Correct 5 ms 344 KB Correct! Number of queries: 800
11 Correct 4 ms 448 KB Correct! Number of queries: 600
12 Correct 5 ms 344 KB Correct! Number of queries: 700
13 Correct 5 ms 344 KB Correct! Number of queries: 700
14 Correct 5 ms 344 KB Correct! Number of queries: 700
15 Correct 5 ms 344 KB Correct! Number of queries: 800
16 Correct 4 ms 344 KB Correct! Number of queries: 600
17 Incorrect 123 ms 688 KB Is not a permutation
18 Halted 0 ms 0 KB -