oj.uz

Submission #160311

# Submission time Handle Problem Language Result Execution time Memory
160311 2019-10-27T01:22:24 Z model_code Mouse (info1cup19_mouse) C++17
100 / 100
 78 ms 504 KB 
/*
Oncescu Costin NlogN - 100 (divide&conquer instead of several binary searches)
*/
#include<bits/stdc++.h>
#include "grader.h"

using namespace std;

static int N;
//mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng (-3090495);
vector < int > p, v[2019];

void setPair (int i, int j)
{
    v[i].push_back (j);
    v[j].push_back (i);
}

int query2 (vector < int > v)
{
    int ans = query (v);
    if (ans == N)
        exit (0);
    return ans;
}

pair < int, int > pairs[2018];
int nr = 0;
int query (int l, int r)
{
    for (int i=l; i<=r; i++)
        swap (p[pairs[i].first - 1], p[pairs[i].second - 1]);
    int ans = query2 (p);
    for (int i=l; i<=r; i++)
        swap (p[pairs[i].first - 1], p[pairs[i].second - 1]);
    return ans;
}

void divide (int l, int r, int sum)
{
    if (sum == 0) return ;
    if (l == r)
    {
        setPair (pairs[l].first, pairs[l].second);
        return ;
    }
    int mid = (l + r) >> 1, ansL = query (l, mid), ansR = sum - ansL;
    divide (l, mid, ansL);
    divide (mid + 1, r, ansR);
}

void findPairs (int sum)
{
    nr = 0;
    for (int i=0; i<N; i++)
    {
        int j = (sum + N - i) % N;
        if (i < j)
            pairs[++nr] = {i + 1, j + 1};
    }
    divide (1, nr, query (1, nr));
}

bool ap[2019];
void dfs (int nod, vector < pair < int, int > > &ip)
{
    ip.push_back ({nod, p[nod - 1]}), ap[nod] = 1;
    for (auto it : v[nod])
        if (ap[it] == 0)
            dfs (it, ip);
}

void finish ()
{
    for (int i=1; i<=N; i++)
        ap[i] = 0;
    vector < int > ans (N, 0);
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            vector < pair < int, int > > ip;
            dfs (i, ip);
            int L = ip.size ();
            for (int j=0; j<L; j++)
                p[ip[j].first - 1] = ip[(j + 1) % L].second;
            if (query2 (p) > 0)
            {
                for (int j=0; j<L; j++)
                    ans[ip[j].first - 1] = ip[(j + 1) % L].second;
            }
            else
            {
                for (int j=0; j<L; j++)
                    ans[ip[j].first - 1] = ip[(j + L - 1) % L].second;
            }
            for (auto pr : ip)
                p[pr.first - 1] = pr.second;
        }
    query2 (ans);
}

void solve (int nn)
{
    N = nn;
    for (int i=1; i<=N; i++)
        v[i].clear ();
    p = vector < int > (N, 0);
    for (int i=0; i<N; i++)
        p[i] = i + 1;
    while (1)
    {
        shuffle (p.begin (), p.end (), rng);
        if (query2 (p) == 0)
            break;
    }
    for (int s=0; s<N; s++)
        findPairs (s);
    finish ();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Correct! Number of queries: 19
2 Correct 5 ms 248 KB Correct! Number of queries: 12
3 Correct 5 ms 376 KB Correct! Number of queries: 15
4 Correct 5 ms 376 KB Correct! Number of queries: 17
5 Correct 5 ms 248 KB Correct! Number of queries: 21
6 Correct 5 ms 504 KB Correct! Number of queries: 21

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Correct! Number of queries: 19
2 Correct 5 ms 248 KB Correct! Number of queries: 12
3 Correct 5 ms 376 KB Correct! Number of queries: 15
4 Correct 5 ms 376 KB Correct! Number of queries: 17
5 Correct 5 ms 248 KB Correct! Number of queries: 21
6 Correct 5 ms 504 KB Correct! Number of queries: 21
7 Correct 10 ms 376 KB Correct! Number of queries: 300
8 Correct 10 ms 376 KB Correct! Number of queries: 300
9 Correct 7 ms 376 KB Correct! Number of queries: 300
10 Correct 8 ms 376 KB Correct! Number of queries: 300
11 Correct 8 ms 376 KB Correct! Number of queries: 300
12 Correct 9 ms 380 KB Correct! Number of queries: 300
13 Correct 9 ms 376 KB Correct! Number of queries: 300
14 Correct 10 ms 376 KB Correct! Number of queries: 300
15 Correct 10 ms 376 KB Correct! Number of queries: 300
16 Correct 9 ms 376 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Correct! Number of queries: 19
2 Correct 5 ms 248 KB Correct! Number of queries: 12
3 Correct 5 ms 376 KB Correct! Number of queries: 15
4 Correct 5 ms 376 KB Correct! Number of queries: 17
5 Correct 5 ms 248 KB Correct! Number of queries: 21
6 Correct 5 ms 504 KB Correct! Number of queries: 21
7 Correct 10 ms 376 KB Correct! Number of queries: 300
8 Correct 10 ms 376 KB Correct! Number of queries: 300
9 Correct 7 ms 376 KB Correct! Number of queries: 300
10 Correct 8 ms 376 KB Correct! Number of queries: 300
11 Correct 8 ms 376 KB Correct! Number of queries: 300
12 Correct 9 ms 380 KB Correct! Number of queries: 300
13 Correct 9 ms 376 KB Correct! Number of queries: 300
14 Correct 10 ms 376 KB Correct! Number of queries: 300
15 Correct 10 ms 376 KB Correct! Number of queries: 300
16 Correct 9 ms 376 KB Correct! Number of queries: 300
17 Correct 78 ms 380 KB Correct! Number of queries: 1900
18 Correct 69 ms 376 KB Correct! Number of queries: 1800
19 Correct 68 ms 384 KB Correct! Number of queries: 1800
20 Correct 73 ms 392 KB Correct! Number of queries: 1900
21 Correct 63 ms 440 KB Correct! Number of queries: 1800
22 Correct 71 ms 388 KB Correct! Number of queries: 1800
23 Correct 65 ms 456 KB Correct! Number of queries: 1800
24 Correct 61 ms 376 KB Correct! Number of queries: 1900
25 Correct 72 ms 392 KB Correct! Number of queries: 1900
26 Correct 76 ms 384 KB Correct! Number of queries: 1900