Submission #429573

#	Time	Username	Problem	Language	Result	Execution time	Memory
429573		lyc	Park (JOI17_park)	C++14	100 / 100	540 ms	808 KiB

park

#include "park.h"

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

static int Place[1400];

const int mxN = 1405;
vector<int> solved, rem, stk, al[mxN];
int N, ban[mxN], vis[mxN];

void myans(int i, int j) {
    //TRACE("ANSWER" _ i _ j);
    if (i > j) swap(i,j);
    al[i].push_back(j);
    al[j].push_back(i);
    Answer(i,j);
}

bool myask(int i, int j, vector<int> v) {
    if (i > j) swap(i,j);
    v.push_back(i);
    v.push_back(j);

    for (int& x : v) Place[x] = 1;
    int ret = Ask(i,j,Place);
    for (int& x : v) Place[x] = 0;
    return ret;
}

void solveLine(int l, int r) {
    //TRACE("LINE" _ l _ r);
    vector<int> line;
    line.push_back(l);
    line.push_back(r);
    while (l != r) {
        int u = *(++find(ALL(line),l));
        while (true) {
            //TRACE("CHECK" _ l _ u);
            if (myask(l,u,solved)) {
                l = u;
                break;
            }

            int lo = -1, hi = SZ(rem);
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;

                vector<int> v2(solved);
                FOR(i,0,mid) v2.push_back(rem[i]);
                if (myask(l,u,v2)) hi = mid;
                else lo = mid;
            }
            u = rem[hi];

            assert(find(ALL(rem),u) != rem.end());
            rem.erase(find(ALL(rem),u));
            line.insert(find(ALL(line),l)+1,u);
        }
    }
    //cerr << "line: "; for (int& x : line) { cerr << x << ' '; } cerr << endl;
    //cerr << "rem: "; for (int& x : rem) { cerr << x << ' '; } cerr << endl;
    line.pop_back();
    for (int& x : line) stk.push_back(x);
}

void dfs(int u, vector<int>& cc) {
    vis[u] = 1; cc.push_back(u);
    for (int& v : al[u]) if (!ban[v] && !vis[v]) dfs(v,cc);
}

void solveComp(int u, vector<int> cc) {
    //TRACE("COMP" _ u _ SZ(cc));
    //for (int& x : cc){ cout << x << ' '; } cout << endl;
    int lo = -1, hi = SZ(cc);
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;

        vector<int> v2;
        FOR(i,0,mid) v2.push_back(cc[i]);
        if (myask(u,cc[0],v2)) hi = mid;
        else lo = mid;
    }
    int v = cc[hi];
    myans(u,v);
    ban[v] = 1;
    fill_n(vis,N,0);
    vector<vector<int>> vcc;
    for (int& x : cc) if (!ban[x] && !vis[x]) {
        vector<int> comp; dfs(x,comp);
        if (myask(u,comp[0],comp)) vcc.push_back(comp);
    }
    for (auto& comp : vcc) solveComp(u,comp);
}

void Detect(int T, int _N) {
    N = _N;
    solved.push_back(0);
    FOR(i,1,N-1) rem.push_back(i);
    while (SZ(solved) < N) {
        if (!SZ(stk)) stk.push_back(rem.back()), rem.pop_back();
        int u = stk.back(); stk.pop_back();
        //TRACE("CHECK" _ u _ solved[0]);
        //for (int& x : solved){ cout << x << ' '; } cout << endl;
        if (!myask(u,solved[0],solved)) {
            solveLine(u,solved[0]);
        } else {
            fill_n(ban,N,0);
            solveComp(u,solved);
            solved.push_back(u);
        }
        //TRACE("OK");
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23