제출 #612543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612543		krit3379	자동 인형 (IOI18_doll)	C++17	100 / 100	212 ms	36460 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 500005

int t[4*N],L[N],R[N],sz,now;
bool sw[N];
vector<int> c,x,y,pos[N];
map<int,int> mp;

int bi(int x){
    int i=1;
    while(i<x)i<<=1;
    return i;
}

int lbi(int x){
    if(x==0)return 0;
    return 1<<(31-__builtin_clz(x));
}

int bic(int x){
    int i=1,cnt=0;
    while(i<x)i<<=1,cnt++;
    return cnt;
}

void cre(int x,int l,int r,int cnt){
    if(l==r){t[x]=l>cnt;return ;}
    int mid=(l+r)/2;
    cre(x*2,l,mid,cnt);
    cre(x*2+1,mid+1,r,cnt);
    t[x]=t[x*2]+t[x*2+1];
}

void sol(int x,int l,int r){
    mp[x];
    if(l+1==r){
        if(!t[x*2])L[x]=1;
        return ;
    }
    int mid=(l+r)/2;
    if(!t[x*2])L[x]=1;
    else L[x]=x*2,sol(x*2,l,mid);
    R[x]=x*2+1;
    sol(x*2+1,mid+1,r);
}

void dfs(int s,vector<int> &a){
    if(now>=a.size())return ;
    if(!sw[s]){
        sw[s]^=1;
        if(!L[s]){
            L[s]=-a[now++];
            dfs(1,a);
        }
        else dfs(L[s],a);
    }
    else{
        sw[s]^=1;
        if(!R[s]){
            R[s]=-a[now++];
            dfs(1,a);
        }
        else dfs(R[s],a);
    }
}

void create_circuit(int m,vector<int> a){
    int n,i;
    a.push_back(0);
    n=a.size();
    c.resize(m+1);
    for(i=0;i<=m;i++)c[i]=-1;
    cre(1,1,bi(n),bi(n)-n);
    sol(1,1,bi(n));
    dfs(1,a);
    for(auto &[x,y]:mp)y=--sz;
    for(auto [key,val]:mp){
        if(L[key]>0)x.push_back(mp[L[key]]);
        else x.push_back(-L[key]);
        if(R[key]>0)y.push_back(mp[R[key]]);
        else y.push_back(-R[key]);
    }
    answer(c,x,y);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void dfs(int, std::vector<int>&)':
doll.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if(now>=a.size())return ;
      |        ~~~^~~~~~~~~~

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