답안 #166345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
166345 2019-12-01T15:27:51 Z georgerapeanu 도서관 (JOI18_library) C++11
0 / 100
630 ms 504 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);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 312 KB # of queries: 2796
2 Correct 58 ms 376 KB # of queries: 2780
3 Correct 62 ms 248 KB # of queries: 2926
4 Correct 59 ms 380 KB # of queries: 2926
5 Correct 47 ms 316 KB # of queries: 2932
6 Correct 50 ms 316 KB # of queries: 2929
7 Correct 57 ms 248 KB # of queries: 2922
8 Correct 36 ms 248 KB # of queries: 2770
9 Correct 37 ms 400 KB # of queries: 2919
10 Correct 34 ms 248 KB # of queries: 1717
11 Incorrect 6 ms 248 KB Wrong Answer [4]
12 Correct 2 ms 248 KB # of queries: 0
13 Correct 2 ms 376 KB # of queries: 3
14 Correct 2 ms 376 KB # of queries: 10
15 Correct 3 ms 376 KB # of queries: 102
16 Correct 5 ms 376 KB # of queries: 230
# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 312 KB # of queries: 2796
2 Correct 58 ms 376 KB # of queries: 2780
3 Correct 62 ms 248 KB # of queries: 2926
4 Correct 59 ms 380 KB # of queries: 2926
5 Correct 47 ms 316 KB # of queries: 2932
6 Correct 50 ms 316 KB # of queries: 2929
7 Correct 57 ms 248 KB # of queries: 2922
8 Correct 36 ms 248 KB # of queries: 2770
9 Correct 37 ms 400 KB # of queries: 2919
10 Correct 34 ms 248 KB # of queries: 1717
11 Incorrect 6 ms 248 KB Wrong Answer [4]
12 Correct 2 ms 248 KB # of queries: 0
13 Correct 2 ms 376 KB # of queries: 3
14 Correct 2 ms 376 KB # of queries: 10
15 Correct 3 ms 376 KB # of queries: 102
16 Correct 5 ms 376 KB # of queries: 230
17 Correct 608 ms 376 KB # of queries: 19288
18 Correct 587 ms 400 KB # of queries: 19031
19 Correct 630 ms 376 KB # of queries: 19257
20 Correct 524 ms 424 KB # of queries: 18011
21 Correct 504 ms 376 KB # of queries: 16930
22 Correct 615 ms 376 KB # of queries: 19275
23 Correct 619 ms 504 KB # of queries: 19230
24 Correct 209 ms 248 KB # of queries: 8882
25 Correct 580 ms 424 KB # of queries: 18817
26 Correct 601 ms 428 KB # of queries: 17610
27 Correct 212 ms 380 KB # of queries: 8849
28 Correct 552 ms 464 KB # of queries: 18932
29 Correct 551 ms 380 KB # of queries: 18911
30 Correct 593 ms 452 KB # of queries: 18932