oj.uz

Submission #696948

# Submission time Handle Problem Language Result Execution time Memory
696948 2023-02-07T16:41:53 Z stevancv Library (JOI18_library) C++14
100 / 100
 269 ms 588 KB 
#include <bits/stdc++.h>
#include "library.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e3 + 2;
const int inf = 2e9;
void Solve(int n) {
    vector<int> init(n), pref(n);
    for (int i = 0; i < n; i++) {
        init[i] = 1;
        pref[i] = Query(init);
    }
  	if (n == 1) {
    	Answer({1});
      	return;
    } 
  	vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        if (pref[i] > pref[i - 1]) continue;
        int l = 0, r = i - 1, pos = -1, spos = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            vector<int> t(n);
            for (int j = 0; j <= mid; j++) t[j] = 1;
            t[i] = 1;
            if (pref[mid] >= Query(t)) {
                pos = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        g[pos].push_back(i);
        g[i].push_back(pos);
        if (pref[i] == pref[i - 1]) continue;
        l = pos + 1, r = i - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            vector<int> t(n);
            for (int j = 0; j <= mid; j++) t[j] = 1;
            t[i] = 1;
            if (pref[mid] - 1 == Query(t)) {
                spos = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        g[spos].push_back(i);
        g[i].push_back(spos);
    }
    int root = -1;
    for (int i = 0; i < n; i++) if (g[i].size() == 1) root = i;
  	for (int i = 0; i < n; i++) assert(1 <= g[i].size() && g[i].size() <= 2);
    vector<int> ans;
    function<void(int, int)> Dfs = [&] (int s, int e) {
        ans.push_back(s + 1);
        for (int u : g[s]) {
            if (u == e) continue;
            Dfs(u, s);
        }
    };
    Dfs(root, -1);
    Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:27:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             int mid = l + r >> 1;
      |                       ~~^~~
library.cpp:42:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 292 KB # of queries: 1466
2 Correct 14 ms 296 KB # of queries: 1468
3 Correct 25 ms 288 KB # of queries: 1535
4 Correct 23 ms 304 KB # of queries: 1546
5 Correct 20 ms 208 KB # of queries: 1546
6 Correct 23 ms 296 KB # of queries: 1530
7 Correct 22 ms 292 KB # of queries: 1544
8 Correct 20 ms 312 KB # of queries: 1461
9 Correct 20 ms 308 KB # of queries: 1550
10 Correct 8 ms 308 KB # of queries: 909
11 Correct 0 ms 208 KB # of queries: 1
12 Correct 0 ms 208 KB # of queries: 3
13 Correct 0 ms 208 KB # of queries: 5
14 Correct 1 ms 208 KB # of queries: 8
15 Correct 1 ms 208 KB # of queries: 57
16 Correct 2 ms 208 KB # of queries: 131

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 292 KB # of queries: 1466
2 Correct 14 ms 296 KB # of queries: 1468
3 Correct 25 ms 288 KB # of queries: 1535
4 Correct 23 ms 304 KB # of queries: 1546
5 Correct 20 ms 208 KB # of queries: 1546
6 Correct 23 ms 296 KB # of queries: 1530
7 Correct 22 ms 292 KB # of queries: 1544
8 Correct 20 ms 312 KB # of queries: 1461
9 Correct 20 ms 308 KB # of queries: 1550
10 Correct 8 ms 308 KB # of queries: 909
11 Correct 0 ms 208 KB # of queries: 1
12 Correct 0 ms 208 KB # of queries: 3
13 Correct 0 ms 208 KB # of queries: 5
14 Correct 1 ms 208 KB # of queries: 8
15 Correct 1 ms 208 KB # of queries: 57
16 Correct 2 ms 208 KB # of queries: 131
17 Correct 269 ms 360 KB # of queries: 10045
18 Correct 256 ms 340 KB # of queries: 9941
19 Correct 251 ms 588 KB # of queries: 10044
20 Correct 225 ms 336 KB # of queries: 9361
21 Correct 208 ms 308 KB # of queries: 8820
22 Correct 241 ms 476 KB # of queries: 10071
23 Correct 248 ms 344 KB # of queries: 10040
24 Correct 91 ms 424 KB # of queries: 4669
25 Correct 258 ms 344 KB # of queries: 9836
26 Correct 196 ms 336 KB # of queries: 9176
27 Correct 64 ms 432 KB # of queries: 4653
28 Correct 217 ms 340 KB # of queries: 9977
29 Correct 219 ms 328 KB # of queries: 9966
30 Correct 228 ms 428 KB # of queries: 9977