Submission #290066

#	Time	Username	Problem	Language	Result	Execution time	Memory
290066		dandrozavr	Mechanical Doll (IOI18_doll)	C++14	39 / 100	272 ms	28376 KiB

doll

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

#define pb push_back
#define F first
#define S second
#define _ <<" "<<
#define pii pair < int , int >

using namespace std;

struct seg_tree{
    vector < int > t, num;
    vector < bool > l, r;
    int n, len, how = 1, bad = 0;
    seg_tree(){n = len = 0;};
    seg_tree(int _n){
        n = _n;
        len = 1;
        while(len <= n) len <<= 1;
        t.resize(len << 1 | 1);
        l.resize(len << 1 | 1);
        r.resize(len << 1 | 1);
        num.resize(len << 1 | 1);
        for (int i = 0; i < num.size(); ++i)
            num[i] = i;
    };

    void way(int v, int tl, int tr){
        if (!t[v]){
            t[v] = 2;
        } else
        if (t[v] == 1) t[v] = 2; else t[v] = 1;
        if (tl == tr){
            t[v] = how++;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (t[v] == 1){
            way(v << 1, tl, tm);
            l[v] = 1;
        }else{
            way(v << 1 | 1, tm + 1, tr);
            r[v] = 1;
        }
    }
};

vector < int > g[(int)(1e5 + 5)];
void create_circuit (int m, vector < int > a) {
    int n = a.size();
    a.pb(0);
    vector < int > c;
    for (int i = 1; i <= n; ++i){
//        cout << a[i - 1] << endl;
        g[a[i - 1]].pb(a[i]);
    }
    g[0].pb(a[0]);
    int now = 1;
    vector < pii > swit;
    for (int i = 0; i <= m; ++i){
        int sz = g[i].size();
        if (!sz){
            c.pb(0);
            continue;
        }
        if (sz == 1){
            c.pb(g[i][0]);
        } else {
            vector < int > all;
            for (int j = 0; j < sz; ++j) all.pb(g[i][j]);
            seg_tree t;
            t = seg_tree(sz);

            int cnt = 0;
            for (int i = 0; i < sz; ++i){
                t.way(1, 0, t.len - 1);
            }
            vector < int > vis;
            vector < int > q;
            reverse(all.begin(), all.end());
            for (int i = t.t.size() - 1; i >= 1; --i)
                if (t.t[i]){
                    if (!t.r[i]){
                        t.num[i] = -all[t.t[i] - 1];
                        continue;
                    }
                    if (!t.l[i])
                        t.num[i << 1] = 1;
                    vis.pb(i);
                    q.pb(i);
                    if (t.num[i << 1] > 0) q.pb(t.num[i << 1]);
                    if (t.num[i << 1 | 1] > 0) q.pb(t.num[i << 1 | 1]);
                }
            sort(q.begin(), q.end());
            q.resize(unique(q.begin(), q.end()) - q.begin());
            unordered_map < int , int > mp;
            reverse(vis.begin(), vis.end());
            for (int i : q) mp[i] = now++;
            for (int i : vis){
                int f = t.num[i << 1];
                if (mp.count(f)) f = mp[f];
                int s = t.num[i << 1 | 1];
                if (mp.count(s)) s = mp[s];
                swit.pb({-f, -s});
//                cout << i _ -f _ -s << endl;
            }
//            cout << vis.size() _ now << endl;
//            for (int i = 1; i < t.num.size(); ++i)
//                cout << t.num[i] _ t.t[i] _ t.l[i] _ t.r[i] << endl;
//            for (auto i : swit)
//                cout << i.F _ i.S << endl;
            c.pb(-mp[t.num[1]]);
        }
    }
//    for (int i : c) cout << i << " ";
//    cout << endl;
    vector < int > X, Y;
    for (int i = 0; i < swit.size(); ++i){
        X.pb(swit[i].F), Y.pb(swit[i].S);
//        cout << X.back() _ Y.back() << endl;
    }
    answer(c, X, Y);
}

Compilation message (stderr)

doll.cpp: In constructor 'seg_tree::seg_tree(int)':
doll.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0; i < num.size(); ++i)
      |                         ~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:78:17: warning: unused variable 'cnt' [-Wunused-variable]
   78 |             int cnt = 0;
      |                 ^~~
doll.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < swit.size(); ++i){
      |                     ~~^~~~~~~~~~~~~

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