oj.uz

답안 #719622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719622 2023-04-06T11:34:56 Z bin9638 자동 인형 (IOI18_doll) C++17
100 / 100
 141 ms 15428 KB 
#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

Compilation message

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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 6984 KB Output is correct
3 Correct 49 ms 6388 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 65 ms 9424 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 6984 KB Output is correct
3 Correct 49 ms 6388 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 65 ms 9424 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 78 ms 10460 KB Output is correct
9 Correct 80 ms 11060 KB Output is correct
10 Correct 111 ms 15428 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 6984 KB Output is correct
3 Correct 49 ms 6388 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 65 ms 9424 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 78 ms 10460 KB Output is correct
9 Correct 80 ms 11060 KB Output is correct
10 Correct 111 ms 15428 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 114 ms 14780 KB Output is correct
15 Correct 77 ms 9568 KB Output is correct
16 Correct 107 ms 14436 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 114 ms 15144 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 74 ms 8768 KB Output is correct
3 Correct 71 ms 8704 KB Output is correct
4 Correct 101 ms 13164 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 74 ms 8768 KB Output is correct
3 Correct 71 ms 8704 KB Output is correct
4 Correct 101 ms 13164 KB Output is correct
5 Correct 116 ms 14248 KB Output is correct
6 Correct 109 ms 13960 KB Output is correct
7 Correct 104 ms 14184 KB Output is correct
8 Correct 103 ms 13828 KB Output is correct
9 Correct 66 ms 8844 KB Output is correct
10 Correct 105 ms 13808 KB Output is correct
11 Correct 108 ms 13572 KB Output is correct
12 Correct 68 ms 9048 KB Output is correct
13 Correct 79 ms 9236 KB Output is correct
14 Correct 75 ms 9300 KB Output is correct
15 Correct 71 ms 9392 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 62 ms 8944 KB Output is correct
18 Correct 71 ms 9088 KB Output is correct
19 Correct 72 ms 9020 KB Output is correct
20 Correct 112 ms 13716 KB Output is correct
21 Correct 102 ms 13632 KB Output is correct
22 Correct 141 ms 13612 KB Output is correct