Submission #637186

#	Time	Username	Problem	Language	Result	Execution time	Memory
637186		stevancv	자동 인형 (IOI18_doll)	C++14	12 / 100	124 ms	8188 KiB

doll

#include <bits/stdc++.h>
#include "doll.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 = 2e5 + 2;
const int mod = 1e9 + 7;
int val[N];
int lc[2 * N], rc[2 * N], root, tsz, bound;
void Create(int &c, int l, int r) {
    if (r < bound) {c = root; return;}
    if (l == r) {c = -val[l]; return;}
    c = ++tsz;
    int mid = l + r >> 1;
    Create(lc[c], l, mid);
    Create(rc[c], mid + 1, r);
}
void create_circuit(int m, vector<int> a) {
    a.push_back(0);
    int n = a.size();
    int x = 1;
    while (x < n) x *= 2;
    vector<int> id(x);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&] (int i, int j) {
        for (int b = 0; b < 20; b++) {
            int p = (1 << b) & i; int q = (1 << b) & j;
            if (p != q) return p < q;
        }
    });
    vector<pair<int, int>> v;
    for (int i = x - n; i < x; i++) v.push_back({id[i], i});
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) val[v[i].second] = a[i];
    bound = x - n;
    Create(root, 0, x - 1);
    vector<int> c(m + 1, -1);
    vector<int> X, Y;
    for (int i = 1; i <= tsz; i++) {
        X.push_back(-lc[i]);
        Y.push_back(-rc[i]);
    }
    answer(c, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void Create(int&, int, int)':
doll.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
doll.cpp: In lambda function:
doll.cpp:34:5: warning: control reaches end of non-void function [-Wreturn-type]
   34 |     });
      |     ^

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56