oj.uz

답안 #874594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874594 2023-11-17T11:02:39 Z garam1732 도서관 (JOI18_library) C++14
100 / 100
 314 ms 596 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

//#include <iostream>

vector<int> res, v;

void Solve(int n)
{
    for(int i = 0; i < n; i++) res.push_back(i);
    v.resize(n);

	int s = 0, e = n-1;
	while(s < e) {
        //cout << s<<' '<<e<<endl;
        //for(int x : res) cout<<x<<' ';
        //cout<<endl;
        int lb = s, ub = e, mid;
        while(lb < ub) {
            mid = lb+ub>>1;

            for(int i = 0; i < n; i++) v[res[i]] = (lb <= i && i <= mid);
            int x = Query(v);
            for(int i = s; i <= e; i++) v[res[i]] ^= 1;
            int y = Query(v);

            if(x >= y) ub = mid;
            else lb = mid+1;
        }

        //cout<<res[lb]<<endl;

        if(s > 0) {
            for(int i = 0; i < n; i++) v[i] = (i == res[s-1] || i == res[lb]);
            int x = Query(v);
            if(x == 1) swap(res[s++], res[lb]);
            else swap(res[e--], res[lb]);
        }
        else if(e < n-1) {
            for(int i = 0; i < n; i++) v[i] = (i == res[e+1] || i == res[lb]);
            int x = Query(v);
            if(x == 1) swap(res[e--], res[lb]);
            else swap(res[s++], res[lb]);
        }
        else swap(res[s++], res[lb]);
	}

	for(int &x : res) x++;
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             mid = lb+ub>>1;
      |                   ~~^~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 596 KB # of queries: 2582
2 Correct 20 ms 344 KB # of queries: 2565
3 Correct 20 ms 344 KB # of queries: 2714
4 Correct 21 ms 344 KB # of queries: 2706
5 Correct 22 ms 344 KB # of queries: 2714
6 Correct 24 ms 344 KB # of queries: 2708
7 Correct 22 ms 344 KB # of queries: 2710
8 Correct 21 ms 344 KB # of queries: 2599
9 Correct 24 ms 344 KB # of queries: 2715
10 Correct 13 ms 344 KB # of queries: 1591
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 7
14 Correct 0 ms 344 KB # of queries: 12
15 Correct 1 ms 344 KB # of queries: 97
16 Correct 2 ms 344 KB # of queries: 219

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 596 KB # of queries: 2582
2 Correct 20 ms 344 KB # of queries: 2565
3 Correct 20 ms 344 KB # of queries: 2714
4 Correct 21 ms 344 KB # of queries: 2706
5 Correct 22 ms 344 KB # of queries: 2714
6 Correct 24 ms 344 KB # of queries: 2708
7 Correct 22 ms 344 KB # of queries: 2710
8 Correct 21 ms 344 KB # of queries: 2599
9 Correct 24 ms 344 KB # of queries: 2715
10 Correct 13 ms 344 KB # of queries: 1591
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 7
14 Correct 0 ms 344 KB # of queries: 12
15 Correct 1 ms 344 KB # of queries: 97
16 Correct 2 ms 344 KB # of queries: 219
17 Correct 268 ms 344 KB # of queries: 18200
18 Correct 291 ms 344 KB # of queries: 17939
19 Correct 310 ms 344 KB # of queries: 18148
20 Correct 272 ms 344 KB # of queries: 16926
21 Correct 246 ms 344 KB # of queries: 15939
22 Correct 314 ms 344 KB # of queries: 18176
23 Correct 281 ms 344 KB # of queries: 18143
24 Correct 98 ms 344 KB # of queries: 8335
25 Correct 292 ms 344 KB # of queries: 17705
26 Correct 245 ms 344 KB # of queries: 16583
27 Correct 121 ms 344 KB # of queries: 8315
28 Correct 301 ms 344 KB # of queries: 18952
29 Correct 286 ms 344 KB # of queries: 18931
30 Correct 278 ms 344 KB # of queries: 18952