oj.uz

Submission #719613

# Submission time Handle Problem Language Result Execution time Memory
719613 2023-04-06T11:17:31 Z bin9638 Mechanical Doll (IOI18_doll) C++17
10 / 100
 1 ms 212 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,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]=++dem;
    build(node[u].child[0],h-1);
    if(cnt>=q)
        return;
    node[u].child[1]=++dem;
    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 k=ceil(log2(a.size()));
    int moc=++dem;
    build(moc,k-1);
    vector<ii>s;
    while(1)
    {
        ii cc=DFS(moc);
        if(!s.empty()&&s[0]==cc)
            break;
        s.pb(cc);
    }
    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+1];
    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;
    n=cc;
    q=a.size();
    C.resize(n+1,0);
    C[0]=a[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:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<a.size()-1;i++)
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -