Submission #310945

#	Time	Username	Problem	Language	Result	Execution time	Memory
310945		aZvezda	Mechanical Doll (IOI18_doll)	C++14	70.67 / 100	141 ms	10464 KiB

doll

#include "doll.h"

#include <vector>

void create_circuit(int M, std::vector<int> A);

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

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int WRONG_ID = -16969420, ROOT_ID = WRONG_ID + 1;
vector<int> arr;
vector<int> x, y;

pair<int, int> buildTree(int l, int r) {
    if(l == r) {
        //cout << l << " " << r << " " << out(arr[l]) << endl;
        return {arr[l], arr[l] != WRONG_ID};
    }
    int m = (l + r) / 2ll;
    auto lftSon = buildTree(l, m);
    auto rghtSon = buildTree(m + 1, r);
    //cout << l << " " << r << " " << lftSon << " " << rghtSon << endl;

    if(lftSon.second + rghtSon.second == 0) {
        return {WRONG_ID, 0};
    } else {
        x.push_back(lftSon.first);
        y.push_back(rghtSon.first);
        return {-x.size(), lftSon.second + rghtSon.second};
    }
}

int bitInverse(int ind, int pow2) {
    int ret = 0;
    for(int i = 0; i < pow2; i ++) {
        if(ind & (1 << i)) {
            ret |= (1 << (pow2 - 1 - i));
        }
    }
    return ret;
}

void create_circuit(int M, std::vector<int> A) {
    arr = A;
    arr.push_back(WRONG_ID);
    int pow2 = 0;
    while((1 << pow2) < arr.size()) {
        pow2 ++;
    }
    while(arr.size() < (1 << pow2)) {
        arr.push_back(WRONG_ID);
    }
    arr[arr.size() - 1] = 0;
    vector<pair<int, int> > prs;
    for(int i = 0; i < arr.size(); i ++) {
        int inv = bitInverse(i, pow2);
        if(i < A.size()) {
            prs.push_back({inv, -1});
            //cout << out(prs.back()) << endl;
        }
    }
    sort(prs.begin(), prs.end());
    for(int i = 0; i < prs.size(); i ++) {
        prs[i].second = arr[i];
    }
    for(int i = 0; i < prs.size(); i ++) {
        arr[bitInverse(prs[i].first, pow2)] = prs[i].second;
    }
    pow2 = 1 << pow2;
    int root = buildTree(0, pow2 - 1).first;
    vector<int> ptr;
    for(int i = 0; i <= M; i ++) {
        ptr.push_back(root);
    }
    for(int i = 0; i < x.size(); i ++) {
        if(x[i] == WRONG_ID) {
            x[i] = root;
        }
        if(y[i] == WRONG_ID) {
            y[i] = root;
        }
        //cout << -i - 1 << " " << x[i] << " " << y[i] << endl;
    }
    answer(ptr, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     while((1 << pow2) < arr.size()) {
      |           ~~~~~~~~~~~~^~~~~~~~~~~~
doll.cpp:62:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     while(arr.size() < (1 << pow2)) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < arr.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
doll.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if(i < A.size()) {
      |            ~~^~~~~~~~~~
doll.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < prs.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
doll.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0; i < prs.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
doll.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0; i < x.size(); i ++) {
      |                    ~~^~~~~~~~~~

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