oj.uz

Submission #521782

# Submission time Handle Problem Language Result Execution time Memory
521782 2022-02-03T06:14:57 Z qwerasdfzxcl Park (JOI17_park) C++14
67 / 100
 356 ms 708 KB 
#include "park.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

static int Place[1400];
int a[2020];

int ask(int x, int y){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=m;j<(int)ans.size();j++) Place[ans[j]] = 0;

            if (ask(0, i)) r = m-1;
            else l = m+1, idx = m;

            for (int j=m;j<(int)ans.size();j++) Place[ans[j]] = 1;
        }
        ans.insert(ans.begin()+idx+1, i);
    }
    for (int i=0;i<n;i++) a[i] = ans[i];
}

vector<pair<int, int>> D;
int cnt = 1;

void Find(int x){
    //for (auto &p:D) printf("(%d, %d) ", p.first, p.second);
    //printf("\n");
    fill(Place, Place+1400, 1);

    int l = 1, r = cnt-1, idx = 0;
    while(l<=r){
        int m = (l+r)>>1;
        for (int i=m;i<cnt;i++) Place[D[i].first] = 0;

        if (!ask(0, x)) idx = m, l = m+1;
        else r = m-1;

        for (int i=m;i<cnt;i++) Place[D[i].first] = 1;
    }
    answer(D[idx].first, x);

    int pt = 0;
    for (;pt<cnt;pt++) if (D[pt].second > D[idx].second+1) break;
    D.insert(D.begin()+pt, make_pair(x, D[idx].second+1));
    cnt++;
}

void Detect(int T, int N) {
    for (int i=1;i<N;i++) a[i] = i;
    _sort(N);

    //printf("A = ");
    //for (int i=0;i<N;i++) printf("%d ", a[i]);
    //printf("\n");

    D.emplace_back(0, 0);
    for (int i=1;i<N;i++){
        Find(a[i]);
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 460 KB Output is correct
2 Correct 141 ms 432 KB Output is correct
3 Correct 151 ms 416 KB Output is correct
4 Correct 331 ms 432 KB Output is correct
5 Correct 338 ms 444 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 400 KB Output is correct
2 Correct 326 ms 400 KB Output is correct
3 Correct 323 ms 496 KB Output is correct
4 Correct 320 ms 520 KB Output is correct
5 Correct 335 ms 400 KB Output is correct
6 Correct 325 ms 400 KB Output is correct
7 Correct 324 ms 416 KB Output is correct
8 Correct 330 ms 396 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 376 KB Output is correct
2 Correct 326 ms 404 KB Output is correct
3 Correct 295 ms 408 KB Output is correct
4 Correct 330 ms 332 KB Output is correct
5 Correct 306 ms 332 KB Output is correct
6 Correct 298 ms 452 KB Output is correct
7 Correct 307 ms 452 KB Output is correct
8 Correct 313 ms 540 KB Output is correct
9 Correct 326 ms 400 KB Output is correct
10 Correct 315 ms 424 KB Output is correct
11 Correct 276 ms 420 KB Output is correct
12 Correct 314 ms 416 KB Output is correct
13 Correct 343 ms 548 KB Output is correct
14 Correct 303 ms 420 KB Output is correct
15 Correct 356 ms 528 KB Output is correct
16 Correct 323 ms 332 KB Output is correct
17 Correct 331 ms 708 KB Output is correct
18 Correct 325 ms 420 KB Output is correct
19 Correct 320 ms 432 KB Output is correct
20 Correct 325 ms 556 KB Output is correct

Subtask #5
0 / 23.0

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