oj.uz

Submission #696945

# Submission time Handle Problem Language Result Execution time Memory
696945 2023-02-07T16:39:25 Z stevancv Library (JOI18_library) C++14
0 / 100
 26 ms 312 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);
    }
    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(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:23:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |             int mid = l + r >> 1;
      |                       ~~^~~
library.cpp:38:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 296 KB # of queries: 1466
2 Correct 22 ms 312 KB # of queries: 1468
3 Correct 22 ms 296 KB # of queries: 1535
4 Correct 26 ms 308 KB # of queries: 1546
5 Correct 24 ms 208 KB # of queries: 1546
6 Correct 22 ms 288 KB # of queries: 1530
7 Correct 26 ms 308 KB # of queries: 1544
8 Correct 24 ms 312 KB # of queries: 1461
9 Correct 13 ms 300 KB # of queries: 1550
10 Correct 13 ms 208 KB # of queries: 909
11 Incorrect 0 ms 208 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 296 KB # of queries: 1466
2 Correct 22 ms 312 KB # of queries: 1468
3 Correct 22 ms 296 KB # of queries: 1535
4 Correct 26 ms 308 KB # of queries: 1546
5 Correct 24 ms 208 KB # of queries: 1546
6 Correct 22 ms 288 KB # of queries: 1530
7 Correct 26 ms 308 KB # of queries: 1544
8 Correct 24 ms 312 KB # of queries: 1461
9 Correct 13 ms 300 KB # of queries: 1550
10 Correct 13 ms 208 KB # of queries: 909
11 Incorrect 0 ms 208 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -