Submission #624089

#	Time	Username	Problem	Language	Result	Execution time	Memory
624089		baluconisTima	Mechanical Doll (IOI18_doll)	C++14	100 / 100	310 ms	34260 KiB

doll

#pragma GCC optimize("O3")
//#pragma GCC tagret("avx2")
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back
#define ld long double
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll, null_type,
        less<ll>, rb_tree_tag,
        tree_order_statistics_node_update> oset;

mt19937 gen(time(0));

const int MOD = 1e9 + 7;


void answer(vector<int> C, vector<int> X, vector<int> Y);


bool used[400007];
vector<int> X, Y;
ll build(ll gl) {
    if(gl == 0) {
        X.pb(0);
        Y.pb(0);
        return X.size() - 1;
    }
    ll v1 = X.size();
    X.pb(-1);
    Y.pb(-1);
    X[v1] = -build(gl - 1);
    Y[v1] = -build(gl - 1);
    return v1;
}


void go(ll v1, ll l, ll r, ll cr, ll root) {
    v1 = -v1;
    if(l + 1 == r) {
        if(l < cr) {
            X[v1] = root;
        }
        if(r < cr) {
            Y[v1] = root;
        }
        return;
    }
    ll mid = (l + r) / 2;
    go(X[v1], l, mid, cr, root);
    go(Y[v1], mid + 1, r, cr, root);
}

set<ll> recalc(ll v1, ll gl) {
    v1 = -v1;
    set<ll> st1, st2;
    if(gl == 0) {
        st1.insert(X[v1]);
        st2.insert(Y[v1]);
    } else {
        for(auto to: recalc(X[v1], gl - 1)) st1.insert(to);
        for(auto to: recalc(Y[v1], gl - 1)) st2.insert(to);
    }
    if(st1.size() == 1) {
        X[v1] = *st1.begin();
    }
    if(st2.size() == 1) {
        Y[v1] = *st2.begin();
    }
    for(auto to: st2) st1.insert(to);
    while(st1.size() > 2) st1.erase(*st1.rbegin());
    return st1;
}

bool col(ll v1, ll x, ll gl) {
    v1 = -v1;
    if(gl == 0) {
        used[v1] ^= 1;
        if(used[v1]) {
            if(X[v1] != 0) return 0;
            X[v1] = x;
        } else {
            if(Y[v1] != 0) return 0;
            Y[v1] = x;
        }
        return 1;
    }
    bool f = 0;
    if(!used[v1]) f = col(X[v1], x, gl - 1);
    else f = col(Y[v1], x, gl - 1);
    used[v1] ^= 1;
    return f;
}


void dob(ll v1, ll x, ll gl) {
    while(true) {
        if(col(v1, x, gl)) break;
    }
}



void create_circuit(int M, vector<int> B) {
//if(A.size() != 16) exit(-1);
    X.clear();
    Y.clear();
    vector<ll> A;
    for(int i = 1; i < B.size(); i++) {
        A.pb(B[i]);
    }
    A.pb(0);

    vector<int> sl(M + 1, 0);
    X.pb(0);
    Y.pb(0);
    ll now = 0;
    while((2 << now) < A.size()) {
        now++;
    }
    ll root = -build(now);
    for(auto &to: sl) to = root;
    ll d = (2 << now) - A.size();
    go(root, 0, (2 << now) - 1, d, root);

    for(auto to: A) {
        dob(root, to, now);
    }
    recalc(root, now);

    sl[0] = B[0];

set<ll> all;
for(auto to: sl) {
    if(to < 0) all.insert(-to);
}
for(int i = 1; i < X.size(); i++) {
    if(X[i] < 0) all.insert(-X[i]);
    if(Y[i] < 0) all.insert(-Y[i]);
}
map<ll,ll> mp;
ll e = -1;
for(auto to: all) {
    mp[to] = e;
    e--;
}

vector<int> x, y;
for(int i = 1; i < X.size(); i++) {
    if(!all.count(i)) continue;
    if(X[i] >= 0) x.pb(X[i]);
    else
        x.pb(mp[-X[i]]);

    if(Y[i] >= 0) y.pb(Y[i]);
    else
        y.pb(mp[-Y[i]]);
}
for(auto &to: sl) {
    if(to < 0) to = mp[-to];
}
answer(sl, x, y);
}

#ifdef LOCAL
int32_t main() {

}
#endif

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i = 1; i < B.size(); i++) {
      |                    ~~^~~~~~~~~~
doll.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     while((2 << now) < A.size()) {
      |           ~~~~~~~~~~~^~~~~~~~~~
doll.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 | for(int i = 1; i < X.size(); i++) {
      |                ~~^~~~~~~~~~
doll.cpp:157:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 | for(int i = 1; i < X.size(); i++) {
      |                ~~^~~~~~~~~~

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