Submission #413467

#	Time	Username	Problem	Language	Result	Execution time	Memory
413467		xyz	Mechanical Doll (IOI18_doll)	C++17	26 / 100	158 ms	17284 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

const int N = 2e5 + 20;
vector<int> g[N];
int to[N];

bool done[N][2];

void create_circuit(int M, vector<int> A) {
    int n = A.size();
    g[0].push_back(A[0]);
    for(int i = 0; i + 1 < n; i ++)
        g[A[i]].push_back(A[i + 1]);
    g[A[n - 1]].push_back(0);
    vector<pair<int, int>> sw; // switches
    const int Q = 99999999;
    sw.push_back({Q, Q}); // just to make 1-idx
    vector<int> out(M + 1);
    for(int i = 0; i <= M; i ++){
        if(g[i].empty()){
            out[i] = i;
            continue;
        }
        if(g[i].size() == 1){
            out[i] = g[i][0];
            continue;
        }
        out[i] = sw.size();
        int l = sw.size();
        sw.push_back({-out[i], -out[i]});
        int r = sw.size();

        int now = 2;
        while(now * 2 <= g[i].size()){
            for(int j = l; j < r; j ++){
                sw[j].first = -(int)sw.size();
                sw.push_back({-out[i], -out[i]});
                sw[j].second = -(int)sw.size();
                sw.push_back({-out[i], -out[i]});
            }
            l = r;
            r = sw.size();
            now *= 2;
        }
//        cout << "now = " << now << endl;
//        cout << g[i].size() << endl;
        if(now < g[i].size()){
//            cout << "dsad" << endl;
            int need = (now * 2 - (int)g[i].size()) / 2;
//            cout << "remove " << need << endl;
            for(int j = 0; j < need; j ++){
                int v = out[i];
                bool found = false;
                while(!found){
                    int was = v;
                    if(to[v] == 1){
                        if(sw[v].second == -out[i]){
                            done[v][1] = true;
                            found = true;
                        }else{
                            v = -sw[v].second;
                        }
                    }else{
                        if(sw[v].first == -out[i]){
                            done[v][0] = true;
                            found = true;
                        }else{
                            v = -sw[v].first;
                        }
                    }
                    to[was] ^= 1;
                }
            }
//            cout << "part 1" << endl;
            need = (g[i].size() + 1) / 2;
            for(int j = 0; j < need; j ++){
                int v = out[i];
                bool found = false;
                while(!found){
                    int was = v;
                    if(to[v] == 1){
                        if(sw[v].second == -out[i] && !done[v][1]){
//                            cout << "add" << endl;
                            sw[v].second = -(int)sw.size();
                            sw.push_back({-out[i], -out[i]});
                            found = true;
                        }else{
                            v = -sw[v].second;
                        }
                    }else{
                        if(sw[v].first == -out[i] && !done[v][0]){
//                            cout << "add" << endl;
                            sw[v].first = -(int)sw.size();
                            sw.push_back({-out[i], -out[i]});
                            found = true;
                        }else{
                            v = -sw[v].first;
                        }
                    }
                    to[was] ^= 1;
                }
            }
//            cout << "part 2" << endl;
            for(int j = out[i]; j < sw.size(); j ++)
                to[j] = 0;
//            fill(to, to + N, 0);
            need = (now * 2 - (int)g[i].size()) / 2 + (g[i].size() + 1) / 2 * 2 - (int)g[i].size();
//            cout << need << endl;
            for(int j = 0; j < need; j ++){
                int v = out[i];
                bool found = false;
                while(!found){
                    int was = v;
                    if(to[v] == 1){
                        if(sw[v].second == -out[i]){
                            done[v][1] = true;
                            found = true;
                        }else{
                            v = -sw[v].second;
                        }
                    }else{
                        if(sw[v].first == -out[i]){
                            done[v][0] = true;
                            found = true;
                        }else{
                            v = -sw[v].first;
                        }
                    }
                    to[was] ^= 1;
                }
            }
//            cout << "bl9" << endl;
        }
        for(int j = 0; j < g[i].size(); j ++){
            int v = out[i];
            bool found = false;
            while(!found){
                int was = v;
                if(to[v] == 1){
                    if(sw[v].second == -out[i] && !done[v][1]){
                        found = true;
                        sw[v].second = g[i][j];
                    }else{
                        v = -sw[v].second;
                    }
                }else{
                    if(sw[v].first == -out[i] && !done[v][0]){
                        found = true;
                        sw[v].first = g[i][j];
                    }else{
                        v = -sw[v].first;
                    }
                }
                to[was] ^= 1;
            }
        }
        out[i] *= -1;
    }
    int S = sw.size();
    vector<int> X(S - 1), Y(S - 1);
    for(int i = 1; i < S; i ++)
        X[i - 1] = sw[i].first, Y[i - 1] = sw[i].second;
//    for(int i = 0; i <= M; i ++)
//        cout << i << " : " << out[i] << endl;
//    for(int i = 0; i < S - 1; i ++)
//        cout << -(i+1) << " : " << X[i] << "   " << Y[i] << endl;
//    for(int x : X)
//        cout << x << " ";
//    cout << endl;
//    for(int x : Y)
//        cout << x << " ";
//    cout << endl;
    answer(out, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(now * 2 <= g[i].size()){
      |               ~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(now < g[i].size()){
      |            ~~~~^~~~~~~~~~~~~
doll.cpp:106:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for(int j = out[i]; j < sw.size(); j ++)
      |                                 ~~^~~~~~~~~~~
doll.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int j = 0; j < g[i].size(); j ++){
      |                        ~~^~~~~~~~~~~~~

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