oj.uz

답안 #412128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412128 2021-05-26T14:27:33 Z benedict0724 도서관 (JOI18_library) C++17
100 / 100
 390 ms 576 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <assert.h>
#include "library.h"
using namespace std;

vector<int> adj[1002];
int U[1002];
void Solve(int N)
{
	vector<int> M(N);
	M[0] = 1;
	int P = 1;
	for(int i = 1; i < N; i++) {
        int l = 0, r = i-1;
        M[i] = 1;
        int Q = Query(M);
        if(P < Q) { P = Q; continue; }

        while(l < r)
        {
            vector<int> v(N);
            int mid = (l + r)/2;
            for(int j=0;j<=mid;j++) v[j] = 1;
            int A, B;
            A = Query(v);
            v[i] = 1;
            B = Query(v);

            if(A >= B) r = mid;
            else l = mid+1;
        }
        adj[i].push_back(l);
        adj[l].push_back(i);

        if(P == Q) continue;
        l++; r = i-1;
        while(l < r)
        {
            vector<int> v(N);
            int mid = (l + r)/2;
            for(int j=0;j<=mid;j++) v[j] = 1;
            int A, B;
            A = Query(v);
            v[i] = 1;
            B = Query(v);
            if(A > B) r = mid;
            else l = mid+1;
        }

        adj[l].push_back(i);
        adj[i].push_back(l);
        P = Q;
	}

	vector<int> res(N);

	int st = 0;
	for(int i=0;i<N;i++) assert(adj[i].size() <= 2);
	int cnt = 0;
	for(int i=0;i<N;i++) if(adj[i].size() == 1) { st = i; cnt++; }
	// assert(cnt == 2);
    // assert(st >= 0);
	for(int i=0,now=st;i<N;i++)
    {
        res[i] = now+1;
        U[now] = 1;
        for(int nxt : adj[now])
        {
            if(!U[nxt])
            {
                now = nxt;
                break;
            }
        }
    }

	Answer(res);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 456 KB # of queries: 2737
2 Correct 45 ms 200 KB # of queries: 2752
3 Correct 40 ms 200 KB # of queries: 2869
4 Correct 39 ms 200 KB # of queries: 2885
5 Correct 49 ms 200 KB # of queries: 2859
6 Correct 42 ms 200 KB # of queries: 2867
7 Correct 51 ms 308 KB # of queries: 2885
8 Correct 46 ms 200 KB # of queries: 2722
9 Correct 41 ms 316 KB # of queries: 2896
10 Correct 28 ms 200 KB # of queries: 1678
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 92
16 Correct 4 ms 200 KB # of queries: 222

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 456 KB # of queries: 2737
2 Correct 45 ms 200 KB # of queries: 2752
3 Correct 40 ms 200 KB # of queries: 2869
4 Correct 39 ms 200 KB # of queries: 2885
5 Correct 49 ms 200 KB # of queries: 2859
6 Correct 42 ms 200 KB # of queries: 2867
7 Correct 51 ms 308 KB # of queries: 2885
8 Correct 46 ms 200 KB # of queries: 2722
9 Correct 41 ms 316 KB # of queries: 2896
10 Correct 28 ms 200 KB # of queries: 1678
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 92
16 Correct 4 ms 200 KB # of queries: 222
17 Correct 309 ms 460 KB # of queries: 19103
18 Correct 382 ms 324 KB # of queries: 18850
19 Correct 390 ms 568 KB # of queries: 19045
20 Correct 309 ms 432 KB # of queries: 17831
21 Correct 286 ms 576 KB # of queries: 16752
22 Correct 362 ms 452 KB # of queries: 19149
23 Correct 370 ms 452 KB # of queries: 19068
24 Correct 133 ms 312 KB # of queries: 8810
25 Correct 354 ms 332 KB # of queries: 18672
26 Correct 345 ms 324 KB # of queries: 17450
27 Correct 159 ms 316 KB # of queries: 8782
28 Correct 309 ms 456 KB # of queries: 16955
29 Correct 307 ms 328 KB # of queries: 16936
30 Correct 313 ms 328 KB # of queries: 16955