Submission #310900

#	Time	Username	Problem	Language	Result	Execution time	Memory
310900		aZvezda	Mechanical Doll (IOI18_doll)	C++14	37 / 100	143 ms	13576 KiB

doll

#include "doll.h"

#include <vector>

#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) {
        return {arr[l], arr[l] != ROOT_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 {0, ROOT_ID};
    } 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(ROOT_ID);
    int pow2 = 0;
    while((1 << pow2) < arr.size()) {
        pow2 ++;
    }
    while(arr.size() < (1 << pow2)) {
        arr.push_back(ROOT_ID);
    }
    arr[arr.size() - 1] = 0;
    vector<pair<int, int> > prs;
    for(int i = 0; i < arr.size(); i ++) {
        int inv = bitInverse(i, pow2);
        prs.push_back({inv, arr[i]});
    }
    sort(prs.begin(), prs.end());
    for(int i = 0; i < arr.size(); i ++) {
        arr[i] = 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(auto it : ptr) {
    //    cout << it << " ";
    }
    //cout << endl;
    for(int i = 0; i < x.size(); i ++) {
        //cout << -i - 1 << " " << x[i] << " " << y[i] << endl;
        if(x[i] == ROOT_ID) {
            x[i] = root;
        }
        if(y[i] == ROOT_ID) {
            y[i] = root;
        }
    }
    answer(ptr, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     while((1 << pow2) < arr.size()) {
      |           ~~~~~~~~~~~~^~~~~~~~~~~~
doll.cpp:57:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     while(arr.size() < (1 << pow2)) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < arr.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
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:76:14: warning: unused variable 'it' [-Wunused-variable]
   76 |     for(auto it : ptr) {
      |              ^~
doll.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < x.size(); i ++) {
      |                    ~~^~~~~~~~~~

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