oj.uz

Submission #522921

# Submission time Handle Problem Language Result Execution time Memory
522921 2022-02-06T12:58:43 Z qwerasdfzxcl Park (JOI17_park) C++14
100 / 100
 450 ms 856 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<=40000); 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 460 KB Output is correct
3 Correct 11 ms 460 KB Output is correct
4 Correct 26 ms 532 KB Output is correct
5 Correct 40 ms 568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 632 KB Output is correct
2 Correct 252 ms 592 KB Output is correct
3 Correct 246 ms 588 KB Output is correct
4 Correct 432 ms 624 KB Output is correct
5 Correct 423 ms 732 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 596 KB Output is correct
2 Correct 303 ms 600 KB Output is correct
3 Correct 317 ms 604 KB Output is correct
4 Correct 326 ms 592 KB Output is correct
5 Correct 315 ms 720 KB Output is correct
6 Correct 300 ms 592 KB Output is correct
7 Correct 348 ms 700 KB Output is correct
8 Correct 289 ms 612 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 568 KB Output is correct
2 Correct 335 ms 564 KB Output is correct
3 Correct 318 ms 564 KB Output is correct
4 Correct 325 ms 588 KB Output is correct
5 Correct 299 ms 584 KB Output is correct
6 Correct 357 ms 708 KB Output is correct
7 Correct 353 ms 592 KB Output is correct
8 Correct 348 ms 688 KB Output is correct
9 Correct 320 ms 564 KB Output is correct
10 Correct 359 ms 568 KB Output is correct
11 Correct 361 ms 716 KB Output is correct
12 Correct 321 ms 624 KB Output is correct
13 Correct 352 ms 608 KB Output is correct
14 Correct 350 ms 608 KB Output is correct
15 Correct 329 ms 564 KB Output is correct
16 Correct 317 ms 580 KB Output is correct
17 Correct 435 ms 744 KB Output is correct
18 Correct 329 ms 624 KB Output is correct
19 Correct 375 ms 724 KB Output is correct
20 Correct 312 ms 616 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 616 KB Output is correct
2 Correct 382 ms 588 KB Output is correct
3 Correct 372 ms 580 KB Output is correct
4 Correct 347 ms 616 KB Output is correct
5 Correct 406 ms 552 KB Output is correct
6 Correct 430 ms 744 KB Output is correct
7 Correct 376 ms 656 KB Output is correct
8 Correct 368 ms 856 KB Output is correct
9 Correct 361 ms 600 KB Output is correct
10 Correct 361 ms 636 KB Output is correct
11 Correct 334 ms 592 KB Output is correct
12 Correct 367 ms 664 KB Output is correct
13 Correct 363 ms 616 KB Output is correct
14 Correct 385 ms 616 KB Output is correct
15 Correct 385 ms 712 KB Output is correct
16 Correct 303 ms 552 KB Output is correct
17 Correct 418 ms 660 KB Output is correct
18 Correct 347 ms 636 KB Output is correct