oj.uz

Submission #522922

# Submission time Handle Problem Language Result Execution time Memory
522922 2022-02-06T12:59:32 Z qwerasdfzxcl Park (JOI17_park) C++14
100 / 100
 472 ms 768 KB 
#include "park.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
static int Place[1400];
int a[1400], Qcnt;
 
int ask(int x, int y){assert(++Qcnt<=35000); return Ask(min(x, y), max(x, y), Place);}
void answer(int x, int y){Answer(min(x, y), max(x, y));}
 
void _sort(int n){
    vector<int> ans = {0};
 
    for (int i=1;i<n;i++){
        fill(Place, Place+1400, 1);
 
        int l = 1, r = (int)ans.size()-1, idx = 0;
        while(l<=r){
            int m = (l+r)>>1;
            for (int j=0;j<m;j++) Place[ans[j]] = 1;
            for (int j=m;j<(int)ans.size();j++) Place[ans[j]] = 0;
 
            if (ask(0, i)) r = m-1;
            else l = m+1, idx = m;
        }
        ans.insert(ans.begin()+idx+1, i);
    }
    for (int i=0;i<n;i++) a[i] = ans[i];
}
 
vector<int> adj[1400], C, W;
int visited[1400];
 
void dfs(int s){
    if (visited[s]) return;
    visited[s] = 1;
    W.push_back(s);
 
    for (auto &v:adj[s]) if (Place[v]) dfs(v);
}
 
void solve(vector<int> V, int x){
    fill(Place, Place+1400, 0);
    fill(visited, visited+1400, 0);
    Place[x] = 1;
    for (auto &v:V) Place[v] = 1;
 
    if (!ask(x, V[0])) return;
 
    W.clear();
    dfs(V[0]);
    int l = 0, r = (int)V.size()-1, idx = (int)V.size()-1;
    while(l<=r){
        int m = (l+r)>>1;
        for (int i=0;i<=m;i++) Place[W[i]] = 1;
        for (int i=m+1;i<(int)V.size();i++) Place[W[i]] = 0;
 
        if (ask(W[0], x)) idx = m, r = m-1;
        else l = m+1;
    }
    answer(W[idx], x);
    adj[W[idx]].push_back(x);
    adj[x].push_back(W[idx]);
 
    fill(Place, Place+1400, 0);
    fill(visited, visited+1400, 0);
    for (auto &v:V) Place[v] = 1;
    Place[W[idx]] = 0;
 
    vector<int> N;
    for (auto &v:adj[W[idx]]) if (Place[v]) N.push_back(v);
 
    vector<vector<int>> nxt_comp;
    for (auto &nxt:N){
        W.clear();
        dfs(nxt);
        if (!W.empty()) nxt_comp.push_back(W);
    }
 
    for (auto &nV:nxt_comp){
        solve(nV, x);
    }
}
 
void Detect(int T, int N) {
    for (int i=1;i<N;i++) a[i] = i;
    _sort(N);
 
    C.push_back(0);
    for (int i=1;i<N;i++){
        solve(C, a[i]);
        C.push_back(a[i]);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 13 ms 496 KB Output is correct
3 Correct 10 ms 472 KB Output is correct
4 Correct 22 ms 572 KB Output is correct
5 Correct 40 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 644 KB Output is correct
2 Correct 241 ms 580 KB Output is correct
3 Correct 244 ms 644 KB Output is correct
4 Correct 472 ms 736 KB Output is correct
5 Correct 413 ms 748 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 656 KB Output is correct
2 Correct 306 ms 676 KB Output is correct
3 Correct 347 ms 580 KB Output is correct
4 Correct 329 ms 588 KB Output is correct
5 Correct 337 ms 544 KB Output is correct
6 Correct 307 ms 672 KB Output is correct
7 Correct 310 ms 580 KB Output is correct
8 Correct 291 ms 548 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 520 KB Output is correct
2 Correct 299 ms 544 KB Output is correct
3 Correct 313 ms 536 KB Output is correct
4 Correct 320 ms 548 KB Output is correct
5 Correct 304 ms 568 KB Output is correct
6 Correct 402 ms 584 KB Output is correct
7 Correct 346 ms 560 KB Output is correct
8 Correct 324 ms 540 KB Output is correct
9 Correct 318 ms 548 KB Output is correct
10 Correct 382 ms 580 KB Output is correct
11 Correct 326 ms 600 KB Output is correct
12 Correct 321 ms 708 KB Output is correct
13 Correct 375 ms 548 KB Output is correct
14 Correct 352 ms 552 KB Output is correct
15 Correct 318 ms 628 KB Output is correct
16 Correct 336 ms 548 KB Output is correct
17 Correct 450 ms 592 KB Output is correct
18 Correct 337 ms 608 KB Output is correct
19 Correct 372 ms 632 KB Output is correct
20 Correct 318 ms 592 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 676 KB Output is correct
2 Correct 411 ms 632 KB Output is correct
3 Correct 387 ms 544 KB Output is correct
4 Correct 355 ms 608 KB Output is correct
5 Correct 438 ms 680 KB Output is correct
6 Correct 412 ms 608 KB Output is correct
7 Correct 415 ms 564 KB Output is correct
8 Correct 374 ms 580 KB Output is correct
9 Correct 399 ms 608 KB Output is correct
10 Correct 380 ms 568 KB Output is correct
11 Correct 344 ms 544 KB Output is correct
12 Correct 378 ms 568 KB Output is correct
13 Correct 330 ms 588 KB Output is correct
14 Correct 391 ms 640 KB Output is correct
15 Correct 398 ms 608 KB Output is correct
16 Correct 293 ms 532 KB Output is correct
17 Correct 410 ms 768 KB Output is correct
18 Correct 367 ms 568 KB Output is correct