Submission #413477

#	Time	Username	Problem	Language	Result	Execution time	Memory
413477		xyz	자동 인형 (IOI18_doll)	C++17	44.40 / 100	175 ms	11272 KiB

doll

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

const int N = 3e5;
int to[N];

bool done[N][2];

void create_circuit(int M, vector<int> A) {
    int n = A.size();

    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);
    A.push_back(0);
    for(int i = n - 1; i >= 0; i --)
        swap(A[i], A[i + 1]);
    ++ n;
    A.push_back(0);

    int start = sw.size();
    int l = sw.size();
    sw.push_back({-start, -start});
    int r = sw.size();

    int now = 2;
    while(now * 2 <= n){
        for(int j = l; j < r; j ++){
            sw[j].first = -(int)sw.size();
            sw.push_back({-start, -start});
            sw[j].second = -(int)sw.size();
            sw.push_back({-start, -start});
        }
        l = r;
        r = sw.size();
        now *= 2;
    }
    if(now < n){
        int need = (now * 2 - (int)n) / 2;
        for(int j = 0; j < need; j ++){
            int v = start;
            bool found = false;
            while(!found){
                int was = v;
                if(to[v] == 1){
                    if(sw[v].second == -start){
                        done[v][1] = true;
                        found = true;
                    }else{
                        v = -sw[v].second;
                    }
                }else{
                    if(sw[v].first == -start){
                        done[v][0] = true;
                        found = true;
                    }else{
                        v = -sw[v].first;
                    }
                }
                to[was] ^= 1;
            }
        }
        need = (n + 1) / 2;
        for(int j = 0; j < need; j ++){
            int v = start;
            bool found = false;
            while(!found){
                int was = v;
                if(to[v] == 1){
                    if(sw[v].second == -start && !done[v][1]){
                        sw[v].second = -(int)sw.size();
                        sw.push_back({-start, -start});
                        found = true;
                    }else{
                        v = -sw[v].second;
                    }
                }else{
                    if(sw[v].first == -start && !done[v][0]){
                        sw[v].first = -(int)sw.size();
                        sw.push_back({-start, -start});
                        found = true;
                    }else{
                        v = -sw[v].first;
                    }
                }
                to[was] ^= 1;
            }
        }
        for(int j = start; j < sw.size(); j ++)
            to[j] = 0;
        need = (now * 2 - n) / 2 + (n + 1) / 2 * 2 - n;
        for(int j = 0; j < need; j ++){
            int v = start;
            bool found = false;
            while(!found){
                int was = v;
                if(to[v] == 1){
                    if(sw[v].second == -start){
                        done[v][1] = true;
                        found = true;
                    }else{
                        v = -sw[v].second;
                    }
                }else{
                    if(sw[v].first == -start){
                        done[v][0] = true;
                        found = true;
                    }else{
                        v = -sw[v].first;
                    }
                }
                to[was] ^= 1;
            }
        }
    }
    for(int j = 0; j < n; j ++){
        int v = start;
        bool found = false;
        while(!found){
            int was = v;
            if(to[v] == 1){
                if(sw[v].second == -start && !done[v][1]){
                    found = true;
                    done[v][1] = true;
                    sw[v].second = A[j + 1];
                }else{
                    v = -sw[v].second;
                }
            }else{
                if(sw[v].first == -start && !done[v][0]){
                    found = true;
                    done[v][0] = true;
                    sw[v].first = A[j + 1];
                }else{
                    v = -sw[v].first;
                }
            }
            to[was] ^= 1;
        }
    }

    for(int i = 0; i <= M; i ++)
        out[i] = -start;
//    cout << "start " << start << endl;
//        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 < S - 1; i ++){
//        cout << -(i + 1) << " : " << X[i] << " " << Y[i] << endl;
//    }
    answer(out, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int j = start; j < sw.size(); j ++)
      |                            ~~^~~~~~~~~~~

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