oj.uz

Submission #429540

# Submission time Handle Problem Language Result Execution time Memory
429540 2021-06-16T05:49:50 Z lyc Park (JOI17_park) C++14
67 / 100
 539 ms 864 KB 
#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 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;
    for (int& x : cc) if (!ban[x] && !vis[x]) {
        vector<int> comp; dfs(x,comp);
        if (myask(u,comp[0],comp)) solveComp(u,comp);
    }
    ban[v] = 0;
}

void Detect(int T, int 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(vis,N,0);
            solveComp(u,solved);
            solved.push_back(u);
        }
        //TRACE("OK");
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 804 KB Output is correct
2 Correct 415 ms 580 KB Output is correct
3 Correct 374 ms 708 KB Output is correct
4 Correct 433 ms 648 KB Output is correct
5 Correct 442 ms 556 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 584 KB Output is correct
2 Correct 375 ms 684 KB Output is correct
3 Correct 414 ms 588 KB Output is correct
4 Correct 374 ms 580 KB Output is correct
5 Correct 426 ms 592 KB Output is correct
6 Correct 379 ms 552 KB Output is correct
7 Correct 393 ms 576 KB Output is correct
8 Correct 372 ms 596 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 536 KB Output is correct
2 Correct 427 ms 580 KB Output is correct
3 Correct 441 ms 584 KB Output is correct
4 Correct 487 ms 560 KB Output is correct
5 Correct 466 ms 608 KB Output is correct
6 Correct 366 ms 632 KB Output is correct
7 Correct 524 ms 752 KB Output is correct
8 Correct 423 ms 696 KB Output is correct
9 Correct 445 ms 580 KB Output is correct
10 Correct 482 ms 708 KB Output is correct
11 Correct 458 ms 864 KB Output is correct
12 Correct 408 ms 524 KB Output is correct
13 Correct 464 ms 712 KB Output is correct
14 Correct 447 ms 568 KB Output is correct
15 Correct 477 ms 716 KB Output is correct
16 Correct 367 ms 544 KB Output is correct
17 Correct 417 ms 776 KB Output is correct
18 Correct 443 ms 592 KB Output is correct
19 Correct 539 ms 632 KB Output is correct
20 Correct 454 ms 708 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 473 ms 664 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -