답안 #823878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823878 2023-08-13T09:23:57 Z Kahou 도서관 (JOI18_library) C++14
100 / 100
210 ms 1076 KB
#include<bits/stdc++.h>
#include"library.h"
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1050;
int n;
deque<int> dq[MAXN];

vector<int> get(int k) {
        vector<int> out(n);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
                if (dq[i].empty()) continue;
                cnt++;
                if (cnt > k) break;
                for (int x:dq[i]) {
                        out[x-1] = 1;
                }
        }
        return out;
}
int getid(int x) {
        for (int i = 1; i <= n; i++) {
                if (dq[i].empty()) continue;
                x--;
                if (!x) return i;
        }
        return 0;
}

void Solve(int N) {
        n = N;
        int t = 1;
        dq[1].push_back(1);
        vector<int> vc(n);
        for (int i = 2; i <= n; i++) {
                vc = get(t);
                vc[i-1] = 1;
                int nt = Query(vc);
                if (nt > t) {
                        dq[i].push_back(i);
                        t++;
                }
                else if (nt == t) {
                        int dw = 0, up = t;
                        while (up-dw > 1) {
                                int md = (up+dw)>>1;
                                vc = get(md);
                                vc[i-1] = 1;
                                if (Query(vc) > md) dw = md;
                                else up = md;
                        }
                        int id = getid(up);
                        bool flg = 0;
                        if (dq[id].size() > 1) {
                                fill(vc.begin(), vc.end(), 0);
                                for (int x:dq[id]) vc[x-1] = 1;
                                vc[i-1] = 1;
                                vc[dq[id].back()-1] = 0;
                                flg = (Query(vc) > 1);
                        }
                        if (flg) dq[id].push_back(i);
                        else dq[id].push_front(i);
                }
                else if (nt < t) {
                        int dw = 0, up = t;
                        while (up-dw > 1) {
                                int md = (up+dw)>>1;
                                vc = get(md);
                                vc[i-1] = 1;
                                if (Query(vc) > md) dw = md;
                                else up = md;
                        }
                        int A = getid(up);
                        dw = 0, up = t;
                        while (up-dw > 1) {
                                int md = (up+dw)>>1;
                                vc = get(md);
                                vc[i-1] = 1;
                                if (Query(vc) >= md) dw = md;
                                else up = md;
                        }
                        int B = getid(up);

                        bool flgA = 0, flgB = 0;
                        if (dq[A].size() > 1) {
                                fill(vc.begin(), vc.end(), 0);
                                for (int x : dq[A]) vc[x-1] = 1;
                                vc[i-1] = 1;
                                vc[dq[A].back()-1] = 0;
                                flgA = (Query(vc) > 1);
                        }
                        if (dq[B].size() > 1) {
                                fill(vc.begin(), vc.end(), 0);
                                for (int x : dq[B]) vc[x-1] = 1;
                                vc[i-1] = 1;
                                vc[dq[B].back()-1] = 0;
                                flgB = (Query(vc) > 1);
                        }

                        if (flgA) dq[A].push_back(i);
                        else dq[A].push_front(i);

                        if (flgB) reverse(dq[B].begin(), dq[B].end());
                        for (int x:dq[B]) {
                                if (flgA) dq[A].push_back(x);
                                else dq[A].push_front(x);
                        }
                        dq[B].clear();
                        t--;
                }
        }

        vector<int> out;
        for (int x:dq[1]) {
                out.push_back(x);
        }
        Answer(out);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 976 KB # of queries: 1253
2 Correct 13 ms 1008 KB # of queries: 1259
3 Correct 10 ms 976 KB # of queries: 1309
4 Correct 15 ms 1008 KB # of queries: 1315
5 Correct 17 ms 976 KB # of queries: 1320
6 Correct 13 ms 976 KB # of queries: 1303
7 Correct 17 ms 1028 KB # of queries: 1316
8 Correct 19 ms 976 KB # of queries: 1246
9 Correct 18 ms 976 KB # of queries: 1309
10 Correct 10 ms 1016 KB # of queries: 765
11 Correct 1 ms 976 KB # of queries: 0
12 Correct 1 ms 976 KB # of queries: 1
13 Correct 1 ms 976 KB # of queries: 3
14 Correct 1 ms 976 KB # of queries: 6
15 Correct 1 ms 976 KB # of queries: 48
16 Correct 2 ms 1012 KB # of queries: 108
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 976 KB # of queries: 1253
2 Correct 13 ms 1008 KB # of queries: 1259
3 Correct 10 ms 976 KB # of queries: 1309
4 Correct 15 ms 1008 KB # of queries: 1315
5 Correct 17 ms 976 KB # of queries: 1320
6 Correct 13 ms 976 KB # of queries: 1303
7 Correct 17 ms 1028 KB # of queries: 1316
8 Correct 19 ms 976 KB # of queries: 1246
9 Correct 18 ms 976 KB # of queries: 1309
10 Correct 10 ms 1016 KB # of queries: 765
11 Correct 1 ms 976 KB # of queries: 0
12 Correct 1 ms 976 KB # of queries: 1
13 Correct 1 ms 976 KB # of queries: 3
14 Correct 1 ms 976 KB # of queries: 6
15 Correct 1 ms 976 KB # of queries: 48
16 Correct 2 ms 1012 KB # of queries: 108
17 Correct 210 ms 1068 KB # of queries: 8817
18 Correct 174 ms 1072 KB # of queries: 8709
19 Correct 172 ms 1068 KB # of queries: 8767
20 Correct 148 ms 1040 KB # of queries: 8243
21 Correct 153 ms 1072 KB # of queries: 7729
22 Correct 192 ms 1036 KB # of queries: 8825
23 Correct 184 ms 1072 KB # of queries: 8805
24 Correct 53 ms 1036 KB # of queries: 4050
25 Correct 188 ms 1076 KB # of queries: 8624
26 Correct 197 ms 1028 KB # of queries: 8069
27 Correct 68 ms 1028 KB # of queries: 4018
28 Correct 58 ms 1016 KB # of queries: 1997
29 Correct 63 ms 1004 KB # of queries: 1995
30 Correct 45 ms 1004 KB # of queries: 1997