oj.uz

Submission #521783

# Submission time Handle Problem Language Result Execution time Memory
521783 2022-02-03T06:17:40 Z qwerasdfzxcl Park (JOI17_park) C++14
67 / 100
 314 ms 648 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, 0);
    for (auto &p:D) Place[p.first] = 1;
    Place[x] = 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[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 460 KB Output is correct
2 Correct 134 ms 424 KB Output is correct
3 Correct 145 ms 432 KB Output is correct
4 Correct 305 ms 436 KB Output is correct
5 Correct 308 ms 456 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 388 KB Output is correct
2 Correct 223 ms 376 KB Output is correct
3 Correct 235 ms 384 KB Output is correct
4 Correct 225 ms 456 KB Output is correct
5 Correct 239 ms 400 KB Output is correct
6 Correct 227 ms 332 KB Output is correct
7 Correct 225 ms 380 KB Output is correct
8 Correct 232 ms 376 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 332 KB Output is correct
2 Correct 229 ms 384 KB Output is correct
3 Correct 225 ms 388 KB Output is correct
4 Correct 242 ms 388 KB Output is correct
5 Correct 249 ms 452 KB Output is correct
6 Correct 270 ms 416 KB Output is correct
7 Correct 248 ms 404 KB Output is correct
8 Correct 238 ms 644 KB Output is correct
9 Correct 233 ms 384 KB Output is correct
10 Correct 248 ms 404 KB Output is correct
11 Correct 256 ms 648 KB Output is correct
12 Correct 240 ms 332 KB Output is correct
13 Correct 256 ms 384 KB Output is correct
14 Correct 267 ms 332 KB Output is correct
15 Correct 257 ms 380 KB Output is correct
16 Correct 224 ms 384 KB Output is correct
17 Correct 314 ms 564 KB Output is correct
18 Correct 261 ms 332 KB Output is correct
19 Correct 273 ms 412 KB Output is correct
20 Correct 237 ms 392 KB Output is correct

Subtask #5
0 / 23.0

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