oj.uz

답안 #166342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
166342 2019-12-01T15:23:47 Z georgerapeanu 도서관 (JOI18_library) C++11
0 / 100
 663 ms 508 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(viz[edges[j].first] == true && viz[edges[j].second] == false){
                ans.push_back(edges[j].second);
                viz[edges[j].second] = true;
                break;
            }
            else if(viz[edges[j].second] == true && viz[edges[j].first] == false){
                ans.push_back(edges[j].first);
                viz[edges[j].first] = true;
                break;
            }
        }
    }

    Answer(ans);
}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 248 KB # of queries: 2796
2 Correct 54 ms 376 KB # of queries: 2780
3 Correct 38 ms 312 KB # of queries: 2926
4 Correct 69 ms 248 KB # of queries: 2926
5 Correct 58 ms 376 KB # of queries: 2932
6 Correct 72 ms 428 KB # of queries: 2929
7 Correct 58 ms 376 KB # of queries: 2922
8 Correct 48 ms 424 KB # of queries: 2770
9 Correct 54 ms 248 KB # of queries: 2919
10 Correct 29 ms 424 KB # of queries: 1717
11 Incorrect 2 ms 376 KB Wrong Answer [4]
12 Correct 2 ms 248 KB # of queries: 0
13 Correct 2 ms 316 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 10
15 Correct 4 ms 376 KB # of queries: 102
16 Correct 6 ms 376 KB # of queries: 230

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 248 KB # of queries: 2796
2 Correct 54 ms 376 KB # of queries: 2780
3 Correct 38 ms 312 KB # of queries: 2926
4 Correct 69 ms 248 KB # of queries: 2926
5 Correct 58 ms 376 KB # of queries: 2932
6 Correct 72 ms 428 KB # of queries: 2929
7 Correct 58 ms 376 KB # of queries: 2922
8 Correct 48 ms 424 KB # of queries: 2770
9 Correct 54 ms 248 KB # of queries: 2919
10 Correct 29 ms 424 KB # of queries: 1717
11 Incorrect 2 ms 376 KB Wrong Answer [4]
12 Correct 2 ms 248 KB # of queries: 0
13 Correct 2 ms 316 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 10
15 Correct 4 ms 376 KB # of queries: 102
16 Correct 6 ms 376 KB # of queries: 230
17 Correct 538 ms 456 KB # of queries: 19288
18 Correct 663 ms 428 KB # of queries: 19031
19 Correct 616 ms 376 KB # of queries: 19257
20 Correct 560 ms 456 KB # of queries: 18011
21 Correct 507 ms 424 KB # of queries: 16930
22 Correct 566 ms 316 KB # of queries: 19275
23 Correct 610 ms 404 KB # of queries: 19230
24 Correct 198 ms 376 KB # of queries: 8882
25 Correct 573 ms 424 KB # of queries: 18817
26 Correct 500 ms 248 KB # of queries: 17610
27 Correct 195 ms 324 KB # of queries: 8849
28 Correct 583 ms 376 KB # of queries: 18932
29 Correct 593 ms 448 KB # of queries: 18911
30 Correct 596 ms 508 KB # of queries: 18932