Submission #162781

#	Time	Username	Problem	Language	Result	Execution time	Memory
162781		Minnakhmetov	Mechanical Doll (IOI18_doll)	C++14	49 / 100	553 ms	29772 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

#define all(aaa) aaa.begin(), aaa.end()

const int N = 4e5 + 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) {
    if (L == R)
        return 0;
    int v = ++z,
        m = (L + R) >> 1;
    ch[v] = {build(L, m), build(m + 1, R)};
    return -v;
}

void upd(int x, int &v) {
    if (v == 0) {
        v = x;
    }
    else {
        upd(x, ch[-v][state[-v]]);
        state[-v] ^= 1;
    }
}

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;
        while (k < w.size())
            k *= 2;

        build(0, k - 1);

        for (int i = 0; i < k - w.size(); i++)
            upd(root, root);

        for (int x : w) {
            upd(x, root);
        }
    }

    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:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while (k < w.size())
      |                ~~^~~~~~~~~~
doll.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < k - w.size(); i++)
      |                         ~~^~~~~~~~~~~~~~

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