제출 #719602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719602		bin9638	자동 인형 (IOI18_doll)	C++17	53 / 100	183 ms	71712 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 n,q,dem=0,root[N];
vector<int>lis[N];
vector<ii>flow_out[N];
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)
        return;
    node[u].child[0]=++dem;
    node[u].child[1]=++dem;
    build(node[u].child[0],h-1);
    build(node[u].child[1],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 u)
{
    int k=ceil(log2(lis[u].size()));
    dem++;
    C[u]=-dem;
    int moc=dem;
    root[u]=moc;
    build(moc,k-1);
    while(1)
    {
        ii cc=DFS(moc);
        if(!flow_out[u].empty()&&cc==flow_out[u][0])
            break;
        //cout<<"cc\n";
        flow_out[u].pb(cc);
    }
    for(auto cc:flow_out[u])
        node[cc.fs].child[cc.sc]=moc;
    int pos=dem;
    while(!lis[u].empty())
    {
        ii cc=flow_out[u].back();
        flow_out[u].pop_back();
        int i=lis[u].back();
        lis[u].pop_back();
        if(i==q-1)
        {
            node[cc.fs].child[cc.sc]=0;
        }else
        {
            node[cc.fs].child[cc.sc]=-a[i+1];
        }
    }
}

void create_circuit(int cc, vector<int> vec)
{
    a=vec;
    n=cc;
    q=a.size();
  //  cout<<m<<" "<<n<<endl;
    for(int i=0;i<q;i++)
        lis[a[i]].pb(i);
   // for(int i=1;i<=n;i++)cout<<lis[i].size()<<endl;
    C.resize(n+1,0);
    C[0]=a[0];
    for(int i=1;i<=n;i++)
        if(!lis[i].empty())
        {
            if(lis[i].size()==1)
            {
                if(lis[i].back()!=q-1)
                    C[i]=a[lis[i].back()+1];
                continue;
            }
            solve(i);
        }
    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:31:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     assert(X.size()<=q*2);
      |            ~~~~~~~~^~~~~
doll.cpp: In function 'void solve(int)':
doll.cpp:80:9: warning: unused variable 'pos' [-Wunused-variable]
   80 |     int pos=dem;
      |         ^~~

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