제출 #719622

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

doll

#include <bits/stdc++.h>

#ifndef SKY
#include "doll.h"
#endif // SKY

using namespace std;

#define N  1000010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int testcase,n,q,moc,dem=0,cnt=0;
vector<int>a,C,X,Y;

#ifdef SKY
void answer(vector<int>C,vector<int>X,vector<int>Y)
{
    for(auto u:C)cout<<u<<" ";cout<<endl;
    for(int i=0;i<X.size();i++)cout<<X[i]<<" "<<Y[i]<<endl;
}
#endif // SKY

void my_answer(vector<int>C,vector<int>X,vector<int>Y)
{
    assert(X.size()<=q*2);
    answer(C,X,Y);
}

struct haha
{
    int child[2]={},tt=0;
}node[N];

void build(int u,int h)
{
    if(h==0)
    {
        cnt+=2;
        return;
    }
    node[u].child[0]=node[u].child[1]=moc;
    node[u].child[1]=++dem;
    build(node[u].child[1],h-1);
    if(cnt>=q)
        return;
    node[u].child[0]=++dem;
    build(node[u].child[0],h-1);
}

ii DFS(int u)
{
    if(node[u].child[0]==0)
    {
        ii res={u,node[u].tt};
        node[u].tt^=1;
        return res;
    }
    node[u].tt^=1;
    return DFS(node[u].child[(node[u].tt^1)]);
}

void solve()
{
    int k=ceil(log2(a.size()));
    moc=++dem;
    C[0]=-moc;
    build(moc,k-1);
    //cout<<dem<<endl;
    vector<ii>s;
    while(1)
    {
        ii cc=DFS(moc);
        if(!s.empty()&&s[0]==cc)
            break;
        s.pb(cc);
    }
   // for(auto cc:s)cout<<cc.fs<<" "<<cc.sc<<endl;
    for(int i=0;i<q;i++)
        C[a[i]]=-moc;
    for(int i=0;i<a.size()-1;i++)
        node[s[i].fs].child[s[i].sc]=-a[i];
    if(a.size()!=s.size())
    {
        node[s[q-1].fs].child[s[q-1].sc]=moc;
        node[s.back().fs].child[s.back().sc]=0;
    }else
    {
        node[s.back().fs].child[s.back().sc]=0;
    }
}

void create_circuit(int cc, vector<int> vec)
{
    assert(++testcase==1);
    a=vec;
    a.pb(0);
    n=cc;
    q=a.size();
    C.resize(n+1,0);
    solve();
    for(int i=1;i<=dem;i++)
        X.pb(-node[i].child[0]),Y.pb(-node[i].child[1]);
    my_answer(C,X,Y);
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int m,n;
    cin>>m>>n;
    vector<int>a;
    for(int i=1;i<=n;i++)
    {
        int u;
        cin>>u;
        a.pb(u);
    }
    create_circuit(m,a);
    return 0;
}
#endif

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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:1:
doll.cpp: In function 'void my_answer(std::vector<int>, std::vector<int>, std::vector<int>)':
doll.cpp:29:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     assert(X.size()<=q*2);
      |            ~~~~~~~~^~~~~
doll.cpp: In function 'void solve()':
doll.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<a.size()-1;i++)
      |                 ~^~~~~~~~~~~

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