Submission #310956

#	Time	Username	Problem	Language	Result	Execution time	Memory
310956		aZvezda	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	204 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) {
    x.resize(0);
    y.resize(0);
    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;
        }
    }
    x = {2, 1, -1, 8, 3, -4, -3, 9, -8, -13, -13, -9, -7};
    y = {7, 4, -2, 6, 5, -5, -6, -13, -13, 0, -10, -11, -12};
    answer(ptr, x, y);
    return;
    cout << "x = {";
    for(int i = 0; i < x.size(); i ++) {
        cout << x[i];
        if(i != x.size() - 1) {
            cout << ", ";
        }
    }
    cout << "};" << endl;
    cout << "y = {";
    for(int i = 0; i < x.size(); i ++) {
        cout << y[i];
        if(i != y.size() - 1) {
            cout << ", ";
        }
    }
    cout << "};";
    answer(ptr, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while((1 << pow2) < arr.size()) {
      |           ~~~~~~~~~~~~^~~~~~~~~~~~
doll.cpp:64:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     while(arr.size() < (1 << pow2)) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < arr.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
doll.cpp:71:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if(i < A.size()) {
      |            ~~^~~~~~~~~~
doll.cpp:77: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]
   77 |     for(int i = 0; i < prs.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
doll.cpp:80: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]
   80 |     for(int i = 0; i < prs.size(); i ++) {
      |                    ~~^~~~~~~~~~~~
doll.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < x.size(); i ++) {
      |                    ~~^~~~~~~~~~
doll.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < x.size(); i ++) {
      |                    ~~^~~~~~~~~~
doll.cpp:104:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         if(i != x.size() - 1) {
      |            ~~^~~~~~~~~~~~~~~
doll.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < x.size(); i ++) {
      |                    ~~^~~~~~~~~~
doll.cpp:112:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if(i != y.size() - 1) {
      |            ~~^~~~~~~~~~~~~~~

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