Submission #160311

#	Time	Username	Problem	Language	Result	Execution time	Memory
160311		model_code	Mouse (info1cup19_mouse)	C++17	100 / 100	78 ms	504 KiB

mouse

/*
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 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49