oj.uz

답안 #290845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
290845 2020-09-04T13:48:13 Z thebes 도서관 (JOI18_library) C++14
100 / 100
 232 ms 512 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
vvi arr; vi M; int i, j, lo, hi, mid;

inline bool qu(int s,int e){
    fill(M.begin(),M.end(),0);
    for(int i=s;i<=e;i++){
        for(auto v : arr[i]) M[v] = 1;
    }
    return Query(M) != e-s+1;
}

inline bool qu2(int x,int y){
    fill(M.begin(),M.end(),0);
    M[x]=M[y]=1;
    return Query(M)==1;
}

inline vi merge(vi x,vi y){
    if(qu2(x[0],y[0])){
        reverse(x.begin(),x.end());
        for(auto v : y) x.push_back(v);
        return x;
    }
    else if(qu2(x.back(),y.back())){
        reverse(y.begin(),y.end());
        for(auto v : y) x.push_back(v);
        return x;
    }
    else if(qu2(x.back(),y[0])){
        for(auto v : y) x.push_back(v);
        return x;
    }
    else{
        for(auto v : x) y.push_back(v);
        return y;
    }
}

inline void mrg(int x,int y){
    vi a, b;
    a = arr[x], b = arr[y];
    arr.erase(arr.begin()+y);
    arr.erase(arr.begin()+x);
    arr.insert(arr.begin()+y-1,merge(a,b));
}

void Solve(int N){
    arr.resize(N); M.resize(N);
	for(i=0;i<N;i++) arr[i].push_back(i);
	for(i=1;i<(int)arr.size();i++){
        while(i&&qu(0,i)){
            lo = 1, hi = i;
            while(lo<hi){
                mid = (lo+hi)>>1;
                if(qu(mid,i)) lo=mid+1;
                else hi=mid;
            }
            lo--;
            mrg(lo, i); i--;
        }
	}
	for(auto &v : arr[0]) v++;
	Answer(arr[0]);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 380 KB # of queries: 1642
2 Correct 21 ms 376 KB # of queries: 1624
3 Correct 18 ms 376 KB # of queries: 1704
4 Correct 27 ms 468 KB # of queries: 1695
5 Correct 26 ms 384 KB # of queries: 1701
6 Correct 25 ms 384 KB # of queries: 1700
7 Correct 21 ms 376 KB # of queries: 1717
8 Correct 25 ms 376 KB # of queries: 1630
9 Correct 23 ms 384 KB # of queries: 1700
10 Correct 12 ms 376 KB # of queries: 1023
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 2
13 Correct 1 ms 256 KB # of queries: 4
14 Correct 0 ms 256 KB # of queries: 10
15 Correct 2 ms 256 KB # of queries: 73
16 Correct 3 ms 256 KB # of queries: 157

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 380 KB # of queries: 1642
2 Correct 21 ms 376 KB # of queries: 1624
3 Correct 18 ms 376 KB # of queries: 1704
4 Correct 27 ms 468 KB # of queries: 1695
5 Correct 26 ms 384 KB # of queries: 1701
6 Correct 25 ms 384 KB # of queries: 1700
7 Correct 21 ms 376 KB # of queries: 1717
8 Correct 25 ms 376 KB # of queries: 1630
9 Correct 23 ms 384 KB # of queries: 1700
10 Correct 12 ms 376 KB # of queries: 1023
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 2
13 Correct 1 ms 256 KB # of queries: 4
14 Correct 0 ms 256 KB # of queries: 10
15 Correct 2 ms 256 KB # of queries: 73
16 Correct 3 ms 256 KB # of queries: 157
17 Correct 224 ms 384 KB # of queries: 10781
18 Correct 221 ms 384 KB # of queries: 10697
19 Correct 216 ms 384 KB # of queries: 10770
20 Correct 207 ms 512 KB # of queries: 10119
21 Correct 188 ms 384 KB # of queries: 9529
22 Correct 229 ms 384 KB # of queries: 10851
23 Correct 217 ms 384 KB # of queries: 10785
24 Correct 93 ms 384 KB # of queries: 5058
25 Correct 232 ms 384 KB # of queries: 10532
26 Correct 212 ms 384 KB # of queries: 9912
27 Correct 72 ms 384 KB # of queries: 5026
28 Correct 64 ms 384 KB # of queries: 2996
29 Correct 72 ms 384 KB # of queries: 2993
30 Correct 64 ms 384 KB # of queries: 2996