제출 #413468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413468		xyz	자동 인형 (IOI18_doll)	C++17	70.40 / 100	196 ms	22500 KiB

doll

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

const int N = 3e5;
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;
        }
        if(now < g[i].size()){
            int need = (now * 2 - (int)g[i].size()) / 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] = 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;
                }
            }
            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]){
                            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]){
                            sw[v].first = -(int)sw.size();
                            sw.push_back({-out[i], -out[i]});
                            found = true;
                        }else{
                            v = -sw[v].first;
                        }
                    }
                    to[was] ^= 1;
                }
            }
            for(int j = out[i]; j < sw.size(); j ++)
                to[j] = 0;
            need = (now * 2 - (int)g[i].size()) / 2 + (g[i].size() + 1) / 2 * 2 - (int)g[i].size();
            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;
                }
            }
        }
        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;
                        done[v][1] = true;
                        sw[v].second = g[i][j];
                    }else{
                        v = -sw[v].second;
                    }
                }else{
                    if(sw[v].first == -out[i] && !done[v][0]){
                        found = true;
                        done[v][0] = 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;
    answer(out, X, Y);
}

컴파일 시 표준 에러 (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:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(now < g[i].size()){
      |            ~~~~^~~~~~~~~~~~~
doll.cpp:98: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]
   98 |             for(int j = out[i]; j < sw.size(); j ++)
      |                                 ~~^~~~~~~~~~~
doll.cpp:125:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         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: 10.8005494248 / 18
• Subtask 6: 33.6017093216 / 56