Submission #119870

#	Time	Username	Problem	Language	Result	Execution time	Memory
119870		Meloric	Mechanical Doll (IOI18_doll)	C++14	100 / 100	313 ms	100660 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;

struct sw{
    int fi, se, flag;
    vector<int> pos1, pos2;
};
vector<sw> tree;
vector<pair<int, pii>> srt;
vector<int> psums;

int dec(vector<int>& a){
    int ans = 0; int pw = 1;
    for(int i = 0; i < a.size(); i++){
        ans+=a[i]*pw; pw*=2;
    }
    return ans;
}
void build(int v, vector<int> pos){
    if(v>=tree.size())return;
    tree[v].pos1 = pos; tree[v].pos1.pb(0);
    tree[v].pos2 = pos; tree[v].pos2.pb(1);
    build(v*2, tree[v].pos1);
    build(v*2+1, tree[v].pos2);
}
void create_circuit(int m, vector<int> A) {
    int n = A.size();
    vector<int> C; C.assign(m+1, -1);
    int len = 1; int lvl = 2;
    while(1){
        if(lvl >= n+1)break;
        len+=lvl;
        lvl*=2;
    }
    tree.assign(len+1, {-1, -1, 1, {}, {}});
    build(1, {});
    psums.assign(len+1, 1); psums[0] = 0;
    for(int i = 0; i < n+1; i++){
        int id = tree.size()-1-(i/2);
        if(i%2)srt.pb({dec(tree[id].pos1), {id, 1}});
        else srt.pb({dec(tree[id].pos2), {id, 2}});
    }
    A.pb(0);
    sort(srt.begin(), srt.end());
    int j = 0;
    /*
    cout << srt.size() << 's';
    for(auto i : A){
        cout << i << ' ';
    }*/
    for(auto i : srt){
        int id = i.Y.X; int fi = i.Y.Y == 1;
        if(fi){
            tree[id].fi = A[j];
        }else{
            tree[id].se = A[j];
        }
        tree[id].flag = 0;
        j++;
    }
    /*
    for(auto i : tree){
        cout << i.fi <<' '<<i.se<<' '<<i.flag<<'\n';
    }*/
    for(int i = tree.size()-1; i>1; i--){
        if(tree[i].flag)psums[i]=0;
        else tree[i/2].flag = tree[i].flag;
    }/*
    for(auto i : psums)cout << i << ' ';
    cout << '\n';*/
    for(int i = 1; i< len+1; i++){
        psums[i]+=psums[i-1];
    }/*
    for(auto i : psums)cout << i << ' ';
    cout << '\n';*/
    for(int i = tree.size()-1; i > 1; i--){
        if(tree[i].flag)continue;
        if(i%2){
            tree[i/2].se = -psums[i];
        }else{
            tree[i/2].fi = -psums[i];
        }
    }
    vector<int> Xe, Ye;
    for(int i = 1; i< tree.size(); i++){
        if(tree[i].flag)continue;
        Xe.pb(tree[i].fi);
        Ye.pb(tree[i].se);
    }
    answer(C, Xe, Ye);
}

Compilation message (stderr)

doll.cpp: In function 'int dec(std::vector<int>&)':
doll.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
doll.cpp: In function 'void build(int, std::vector<int>)':
doll.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sw>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(v>=tree.size())return;
      |        ~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sw>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 1; i< tree.size(); i++){
      |                    ~^~~~~~~~~~~~~

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