oj.uz

답안 #719602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719602 2023-04-06T10:47:36 Z bin9638 자동 인형 (IOI18_doll) C++17
53 / 100
 183 ms 71712 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 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 44 ms 51544 KB Output is correct
3 Correct 41 ms 51124 KB Output is correct
4 Correct 24 ms 47276 KB Output is correct
5 Correct 34 ms 48852 KB Output is correct
6 Correct 51 ms 53128 KB Output is correct
7 Correct 22 ms 47160 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 44 ms 51544 KB Output is correct
3 Correct 41 ms 51124 KB Output is correct
4 Correct 24 ms 47276 KB Output is correct
5 Correct 34 ms 48852 KB Output is correct
6 Correct 51 ms 53128 KB Output is correct
7 Correct 22 ms 47160 KB Output is correct
8 Correct 80 ms 57128 KB Output is correct
9 Correct 75 ms 56792 KB Output is correct
10 Correct 104 ms 62340 KB Output is correct
11 Correct 23 ms 47180 KB Output is correct
12 Correct 22 ms 47196 KB Output is correct
13 Correct 23 ms 47268 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 44 ms 51544 KB Output is correct
3 Correct 41 ms 51124 KB Output is correct
4 Correct 24 ms 47276 KB Output is correct
5 Correct 34 ms 48852 KB Output is correct
6 Correct 51 ms 53128 KB Output is correct
7 Correct 22 ms 47160 KB Output is correct
8 Correct 80 ms 57128 KB Output is correct
9 Correct 75 ms 56792 KB Output is correct
10 Correct 104 ms 62340 KB Output is correct
11 Correct 23 ms 47180 KB Output is correct
12 Correct 22 ms 47196 KB Output is correct
13 Correct 23 ms 47268 KB Output is correct
14 Correct 132 ms 64684 KB Output is correct
15 Correct 75 ms 56276 KB Output is correct
16 Correct 122 ms 60976 KB Output is correct
17 Correct 22 ms 47188 KB Output is correct
18 Correct 24 ms 47272 KB Output is correct
19 Correct 25 ms 47180 KB Output is correct
20 Correct 107 ms 62884 KB Output is correct
21 Correct 27 ms 47212 KB Output is correct
22 Correct 26 ms 47176 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 47160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 32 ms 47328 KB Output is partially correct
2 Correct 92 ms 56944 KB Output is correct
3 Partially correct 153 ms 65060 KB Output is partially correct
4 Partially correct 140 ms 65824 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 32 ms 47328 KB Output is partially correct
2 Correct 92 ms 56944 KB Output is correct
3 Partially correct 153 ms 65060 KB Output is partially correct
4 Partially correct 140 ms 65824 KB Output is partially correct
5 Partially correct 127 ms 67780 KB Output is partially correct
6 Partially correct 131 ms 69472 KB Output is partially correct
7 Partially correct 129 ms 68972 KB Output is partially correct
8 Partially correct 147 ms 70616 KB Output is partially correct
9 Partially correct 127 ms 62744 KB Output is partially correct
10 Partially correct 183 ms 70364 KB Output is partially correct
11 Partially correct 138 ms 71712 KB Output is partially correct
12 Partially correct 101 ms 63300 KB Output is partially correct
13 Partially correct 96 ms 62016 KB Output is partially correct
14 Partially correct 91 ms 61344 KB Output is partially correct
15 Partially correct 96 ms 60728 KB Output is partially correct
16 Partially correct 26 ms 47680 KB Output is partially correct
17 Partially correct 84 ms 60008 KB Output is partially correct
18 Partially correct 86 ms 60120 KB Output is partially correct
19 Partially correct 89 ms 60920 KB Output is partially correct
20 Partially correct 123 ms 64964 KB Output is partially correct
21 Partially correct 134 ms 68700 KB Output is partially correct
22 Partially correct 110 ms 63852 KB Output is partially correct