Submission #696948

#	Time	Username	Problem	Language	Result	Execution time	Memory
696948		stevancv	Library (JOI18_library)	C++14	100 / 100	269 ms	588 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81