제출 #1219602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219602		inesfi	Mechanical Doll (IOI18_doll)	C++20	53 / 100	64 ms	18600 KiB

doll

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

const int TAILLEMAXI=100*1000+2;
vector<int> vers[TAILLEMAXI];
vector<int> X,Y,prochain;

void create_circuit(int M,vector<int> A) {
    A.push_back(0);
    for (int i=0;i<(int)A.size()-1;i++){
        vers[A[i]].push_back(A[i+1]);
    }
    int compt=-1;
    prochain.push_back(A[0]);
    for (int i=1;i<=M;i++){
        if (vers[i].size()==0){
            prochain.push_back(0);
        }
        else if (vers[i].size()==1){
            prochain.push_back(vers[i][0]);
        }
        else {
            int taille=1;
            while (taille<(int)vers[i].size()){
                taille*=2;
            }
            //cout<<taille<<endl;
            vector<pair<int,int>> arbre={};
            vector<int> etat={};
            arbre.push_back({0,0});
            etat.push_back(0);
            for (int j=1;j<taille/2;j++){
                arbre.push_back({2*j,2*j+1});
                etat.push_back(0);
            }
            for (int j=taille/2;j<taille;j++){
                arbre.push_back({0,0});
                etat.push_back(0);
            }
            int pris=vers[i].size();
            while (pris>1){
                int ec=1;
                while (ec<taille/2){
                    //cout<<42<<" "<<ec<<endl;
                    int anc=ec;
                    if (etat[ec]==0){
                        ec=ec*2;
                    }
                    else {
                        ec=ec*2+1;
                    }
                    etat[anc]+=1;
                    etat[anc]%=2;
                }
                //cout<<ec<<endl;
                if (etat[ec]==0){
                    arbre[ec].first=vers[i][vers[i].size()-pris];
                }
                else {
                    arbre[ec].second=vers[i][vers[i].size()-pris];
                }
                etat[ec]+=1;
                etat[ec]%=2;
                pris--;
            }
            for (int j=1;j<taille;j++){
                if (arbre[j].first==0){
                    arbre[j].first=compt;
                }
                if (arbre[j].second==0){
                    if (j==taille-1){
                        arbre[j].second=vers[i].back();
                    }
                    else {
                        arbre[j].second=compt;
                    }
                }
            }
            //cout<<arbre[1].first<<" "<<arbre[1].second<<endl;
            prochain.push_back(compt);
            for (int i=1;i<taille/2;i++){
                X.push_back(compt-arbre[i].first+1);
                Y.push_back(compt-arbre[i].second+1);
            }
            for (int i=taille/2;i<taille;i++){
                X.push_back(arbre[i].first);
                Y.push_back(arbre[i].second);
            }
            compt-=taille-1;
        }
    }
    /*for (auto a:prochain){
        cout<<a<<" ";
    }
    cout<<endl;
    for (auto a:X){
        cout<<a<<" ";
    }
    cout<<endl;
    for (auto a:Y){
        cout<<a<<" ";
    }
    cout<<endl;*/
    answer(prochain,X,Y);
    //answer({1,-1},{-2,1,1},{-3,-1,0});
    //cout<<vers[1].size()<<endl;
}

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