oj.uz

Submission #166347

# Submission time Handle Problem Language Result Execution time Memory
166347 2019-12-01T15:30:52 Z georgerapeanu Library (JOI18_library) C++11
100 / 100
 644 ms 456 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

const int NMAX = 1e3;

vector<pair<int,int> > edges;
vector<int> for_query;

int my_query(int n,int l,int r){
    for(int i = 0;i < n;i++){
        for_query[i] = (l - 1 <= i && i <= r - 1);
    }
    int ans = Query(for_query);
    ans = (r - l) - (ans - 1);
    for(auto it:edges){
        ans -= (l <= it.first && it.second <= r);
    }
    return ans;
}

bool viz[NMAX + 5];
int gr[NMAX + 5];

void Solve(int n){
    for_query = vector<int>(n,0);

    for(int t = 1;t < n;t++){
        int l = 1,r = n;

        while(r - l > 1){
            int mid = (l + r) / 2;
            if(my_query(n,1,mid) > 0){
                r = mid;
            }
            else{
                l = mid;
            }
        }

        int lst = r;

        l = 1;r = lst;

        while(r - l > 1){
            int mid = (l + r) / 2;
            if(my_query(n,mid,lst) > 0){
                l = mid;
            }
            else{
                r = mid;
            }
        }

        int fst = l;

        edges.push_back({fst,lst});
        gr[fst]++;
        gr[lst]++;
    }

    vector<int> ans;

    for(int i = 1;i <= n;i++){
        if(gr[i] <= 1){
            ans.push_back(i);
            viz[i] = true;
            break;
        }
    }

    for(int i = 0;i < (int)ans.size();i++){
        for(int j = 0;j < (int)edges.size();j++){
            if(edges[j].first == ans[i] && viz[edges[j].second] == false){
                ans.push_back(edges[j].second);
                viz[edges[j].second] = true;
                break;
            }
            else if(edges[j].second == ans[i] && viz[edges[j].first] == false){
                ans.push_back(edges[j].first);
                viz[edges[j].first] = true;
                break;
            }
        }
    }

    Answer(ans);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 328 KB # of queries: 2796
2 Correct 58 ms 316 KB # of queries: 2780
3 Correct 60 ms 376 KB # of queries: 2926
4 Correct 51 ms 316 KB # of queries: 2926
5 Correct 38 ms 316 KB # of queries: 2932
6 Correct 59 ms 316 KB # of queries: 2929
7 Correct 53 ms 320 KB # of queries: 2922
8 Correct 48 ms 376 KB # of queries: 2770
9 Correct 58 ms 376 KB # of queries: 2919
10 Correct 22 ms 312 KB # of queries: 1717
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 0
13 Correct 2 ms 248 KB # of queries: 3
14 Correct 2 ms 316 KB # of queries: 10
15 Correct 3 ms 376 KB # of queries: 102
16 Correct 6 ms 248 KB # of queries: 230

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 328 KB # of queries: 2796
2 Correct 58 ms 316 KB # of queries: 2780
3 Correct 60 ms 376 KB # of queries: 2926
4 Correct 51 ms 316 KB # of queries: 2926
5 Correct 38 ms 316 KB # of queries: 2932
6 Correct 59 ms 316 KB # of queries: 2929
7 Correct 53 ms 320 KB # of queries: 2922
8 Correct 48 ms 376 KB # of queries: 2770
9 Correct 58 ms 376 KB # of queries: 2919
10 Correct 22 ms 312 KB # of queries: 1717
11 Correct 2 ms 248 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 0
13 Correct 2 ms 248 KB # of queries: 3
14 Correct 2 ms 316 KB # of queries: 10
15 Correct 3 ms 376 KB # of queries: 102
16 Correct 6 ms 248 KB # of queries: 230
17 Correct 596 ms 332 KB # of queries: 19288
18 Correct 591 ms 456 KB # of queries: 19031
19 Correct 616 ms 336 KB # of queries: 19257
20 Correct 540 ms 336 KB # of queries: 18011
21 Correct 530 ms 428 KB # of queries: 16930
22 Correct 644 ms 328 KB # of queries: 19275
23 Correct 620 ms 400 KB # of queries: 19230
24 Correct 173 ms 376 KB # of queries: 8882
25 Correct 582 ms 376 KB # of queries: 18817
26 Correct 527 ms 404 KB # of queries: 17610
27 Correct 198 ms 332 KB # of queries: 8849
28 Correct 595 ms 408 KB # of queries: 18932
29 Correct 563 ms 456 KB # of queries: 18911
30 Correct 609 ms 376 KB # of queries: 18932