oj.uz

답안 #624086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624086 2022-08-07T08:26:04 Z radal 도서관 (JOI18_library) C++17
100 / 100
 287 ms 328 KB 
#include <bits/stdc++.h>
#include "library.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e3+10,mod = 998244353,inf = 1e9+10;
int moj[N][2];
void Solve(int n){
    if (n == 1){
        vector<int> ve;
        ve.pb(1);
        Answer(ve);
        return;
    }
    memset(moj,-1,sizeof moj);
    vector<int> ask;
    ask.resize(n);
    rep(i,1,n+1){
        if (moj[i][0] != -1 && moj[i][1] != -1) continue;
        if (moj[i][0] != -1){
            int v = moj[i][0];
            rep(j,0,v){
                if (j == i-1) continue;
                ask[j] = 1;
            }
            rep(j,v,n) ask[j] = 0;
            int x = Query(ask);
            ask[i-1] = 1;
            int y = Query(ask);
            if (y-x == -1){
                int l = i,r = v-1,m;
                while (r-l > 1){
                    m = (l+r) >> 1;
                    ask[i-1] = 0;
                    rep(j,0,m){
                        if (j == i-1) continue;
                        ask[j] = 1;
                    }
                    rep(j,m,n) ask[j] = 0;
                    x = Query(ask);
                    ask[i-1] = 1;
                    y = Query(ask);
                    if (y-x > 0) l = m;
                    else r = m;
                }
                moj[i][1] = r;
                if (moj[r][0] == -1) moj[r][0] = i;
                else moj[r][1] = i;
                continue;
            }
            int l = v,r = n+1,m;
            while (r-l > 1){
                m = (l+r) >> 1;
                ask[i-1] = 0;
                rep(j,0,m){
                    if (j == i-1) continue;
                    ask[j] = 1;
                }
                rep(j,m,n) ask[j] = 0;
                x = Query(ask);
                ask[i-1] = 1;
                y = Query(ask);
                if (y-x == 0) l = m;
                else r = m;
            }
            if (r == n+1) continue;
            moj[i][1] = r;
            if (moj[r][0] == -1) moj[r][0] = i;
            else moj[r][1] = i;
            continue;
        }
        int l = i,r = n+1,m,r2 = n+1,x,y;
        while (r-l > 1){
            m = (l+r) >> 1;
            ask[i-1] = 0;
            rep(j,0,m){
                if (j == i-1) continue;
                ask[j] = 1;
            }
            rep(j,m,n) ask[j] = 0;
            x = Query(ask);
            ask[i-1] = 1;
            y = Query(ask);
            if (y-x == 1) l = m;
            else{
                r = m;
                if (y-x == -1) r2 = m;
            }
        }
        moj[i][0] = r;
        if (moj[r][0] == -1) moj[r][0] = i;
        else moj[r][1] = i;
        l = r;
        r = r2;
        while (r-l > 1){ 
            m = (l+r) >> 1;
            ask[i-1] = 0;
            rep(j,0,m){
                if (j == i-1) continue;
                ask[j] = 1;
            }
            rep(j,m,n) ask[j] = 0;
            x = Query(ask);
            ask[i-1] = 1;
            y = Query(ask);
            if (y-x == 0) l = m;
            else r = m;
        }
        if (r == n+1) continue;
        moj[i][1] = r;
        if (moj[r][0] == -1) moj[r][0] = i;
        else moj[r][1] = i;
    }
    vector<int> ans;
    int cur = 1,perv = -1;
    rep(i,1,n+1) if (moj[i][1] == -1) cur = i;
    while (cur > 0){
        ans.pb(cur);
        if (ans.size() == n) break;
        if (moj[cur][0] == perv){
            perv = cur;
            cur = moj[cur][1];
        }
        else{
            perv = cur;
            cur = moj[cur][0];
        }
    }
    Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:131:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |         if (ans.size() == n) break;
      |             ~~~~~~~~~~~^~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 208 KB # of queries: 2676
2 Correct 22 ms 208 KB # of queries: 2722
3 Correct 40 ms 292 KB # of queries: 2832
4 Correct 29 ms 208 KB # of queries: 2918
5 Correct 35 ms 284 KB # of queries: 2902
6 Correct 31 ms 292 KB # of queries: 2868
7 Correct 40 ms 300 KB # of queries: 2904
8 Correct 33 ms 288 KB # of queries: 2760
9 Correct 38 ms 208 KB # of queries: 2892
10 Correct 23 ms 288 KB # of queries: 1656
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 6
13 Correct 1 ms 208 KB # of queries: 16
14 Correct 1 ms 208 KB # of queries: 16
15 Correct 2 ms 208 KB # of queries: 104
16 Correct 4 ms 208 KB # of queries: 254

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 208 KB # of queries: 2676
2 Correct 22 ms 208 KB # of queries: 2722
3 Correct 40 ms 292 KB # of queries: 2832
4 Correct 29 ms 208 KB # of queries: 2918
5 Correct 35 ms 284 KB # of queries: 2902
6 Correct 31 ms 292 KB # of queries: 2868
7 Correct 40 ms 300 KB # of queries: 2904
8 Correct 33 ms 288 KB # of queries: 2760
9 Correct 38 ms 208 KB # of queries: 2892
10 Correct 23 ms 288 KB # of queries: 1656
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 6
13 Correct 1 ms 208 KB # of queries: 16
14 Correct 1 ms 208 KB # of queries: 16
15 Correct 2 ms 208 KB # of queries: 104
16 Correct 4 ms 208 KB # of queries: 254
17 Correct 287 ms 292 KB # of queries: 18846
18 Correct 261 ms 288 KB # of queries: 18592
19 Correct 285 ms 292 KB # of queries: 18602
20 Correct 256 ms 292 KB # of queries: 17502
21 Correct 225 ms 296 KB # of queries: 16572
22 Correct 263 ms 292 KB # of queries: 18776
23 Correct 276 ms 292 KB # of queries: 18744
24 Correct 120 ms 292 KB # of queries: 8656
25 Correct 265 ms 304 KB # of queries: 18394
26 Correct 201 ms 288 KB # of queries: 17100
27 Correct 105 ms 292 KB # of queries: 8576
28 Correct 252 ms 296 KB # of queries: 18986
29 Correct 271 ms 328 KB # of queries: 18964
30 Correct 233 ms 292 KB # of queries: 18986