Submission #162793

#	Time	Username	Problem	Language	Result	Execution time	Memory
162793		Minnakhmetov	Mechanical Doll (IOI18_doll)	C++14	100 / 100	397 ms	41632 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
 
#define all(aaa) aaa.begin(), aaa.end()
 
const int N = 1e6 + 5;
 
vector<int> tot, tosx, tosy, ct, w;
int z = 0, root = -1;
 
vector<int> ch[N];
int state[N];
 
int build(int L, int R, int &waste) {
    if (R - L + 1 <= waste) {        
        waste -= R - L + 1;
        return -1;
    }
    if (L == R)
        return 0;
    int v = ++z,
        m = (L + R) >> 1;
    ch[v] = {build(L, m, waste), build(m + 1, R, waste)};
    // cout << -v << " " << ch[v][0] << " " << ch[v][1] << "\n";
    return -v;
}
 
void create_circuit(int m, vector<int> a) {
    tot.resize(m + 1);
    ct.resize(m + 1);
 
    a.insert(a.begin(), 0);
    for (int x : a)
        ct[x]++;
    a.push_back(0);
 
    int n = a.size();
 
    // for (int x : a)
    //     cout << x << " ";
    // cout << "\n";
 
    for (int i = 0; i < n - 1; i++) {
        if (ct[a[i]] == 1) {
            tot[a[i]] = a[i + 1];
        }
        else {
            tot[a[i]] = -1;
            w.push_back(a[i + 1]);
        }
    }
 
    // for (int i = 0; i <= m; i++) {
    //     cout << tot[i] << " ";
    // }
    // cout << "\n";
 
 
 
    if (!w.empty()) {
        int k = 1, waste;
        while (k < w.size())
            k *= 2;
        waste = k - w.size();

        build(0, k - 1, waste);
 
        for (int x : w) {
            int y = root, py;
            while (y != 0) {
                py = y;
                y = ch[-py][state[-py]];
                state[-py] ^= 1;
            }
            ch[-py][state[-py] ^ 1] = x;
        }
    }
 
    tosx.resize(z);
    tosy.resize(z);
 
    for (int i = 1; i <= z; i++) {
        tosx[i - 1] = ch[i][0];
        tosy[i - 1] = ch[i][1];
    }
 
    // for (int x : tot)
    //     cout << x << " ";
    // cout << "\n";
    // for (int x : tosx)
    //     cout << x << " ";
    // cout << "\n";
    // for (int x : tosy) 
    //     cout << x << " ";
    // cout << "\n";
 
    answer(tot, tosx, tosy);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while (k < w.size())
      |                ~~^~~~~~~~~~
doll.cpp:76:27: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             ch[-py][state[-py] ^ 1] = x;
      |                           ^~~

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