Submission #109472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
109472	2019-05-06T16:33:03 Z	nikolapesic2802	Mechanical Doll (IOI18_doll)	C++14	16 / 100	152 ms	18060 KB

doll

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

using namespace std;
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
struct node{
    int x,y;
    node(){x=-1;y=-1;}
};
const int NMAX=6e5+5;
vector<node> graf(NMAX);
vector<int> flipped(NMAX);
int stigao;
void build(int tr,int koliko)
{
    if(koliko==0)
        return;
    graf[tr].x=stigao;
    stigao++;
    build(stigao-1,koliko-1);
    graf[tr].y=stigao;
    stigao++;
    build(stigao-1,koliko-1);
}
pair<int,int> get(int tr)
{
    //printf("Getujem %i %i  %i %i\n",tr,flipped[tr],graf[tr].x,graf[tr].y);
    if(flipped[tr])
    {
        flipped[tr]=0;
        if(graf[tr].y==-1)
        {
            return {tr,1};
        }
        else
            return get(graf[tr].y);
    }
    else
    {
        flipped[tr]=1;
        if(graf[tr].x==-1)
        {
            return {tr,0};
        }
        else
            return get(graf[tr].x);
    }
}
void construct(int i,vector<int> d)
{
    //cout << d << i << endl;
    if(d.size()==0)
        d.pb(0);
    if(d.size()==1)
    {
        graf[i].x=d[0];
        return;
    }
    int sz=1;
    while((1<<sz)<(int)d.size())
        sz++;
    graf[i].x=stigao;
    stigao++;
    build(stigao-1,sz-1);
    for(int j=0;j<(1<<sz);j++)
    {
        pair<int,int> t=get(graf[i].x);
        if(t.s)
        {
            if(j==(1<<sz)-1)
            {
                graf[t.f].y=d.back();
                continue;
            }
            if(j>=(int)d.size()-1)
                graf[t.f].y=graf[i].x;
            else
                graf[t.f].y=d[j];
        }
        else
        {
            if(j==(1<<sz)-1)
            {
                graf[t.f].x=d.back();
                continue;
            }
            if(j>=(int)d.size()-1)
                graf[t.f].x=graf[i].x;
            else
                graf[t.f].x=d[j];
        }
    }
    /*for(int i=0;i<NMAX;i++)
    {
        printf("%i: %i %i\n",i,graf[i].x,graf[i].y);
    }*/
}
void create_circuit(int m, vector<int> a)
{
    int n=a.size();
    vector<vector<int> > ide(m+1);
    for(int i=0;i<=m;i++)
        graf[i].y=-1;
    graf[0].x=a[0];
    for(int i=1;i<n;i++)
        ide[a[i-1]].pb(a[i]);
    ide[a.back()].pb(0);
    stigao=m+1;
    for(int i=1;i<=m;i++)
        construct(i,ide[i]);
    vector<int> A,X,Y;
    for(int i=0;i<=m;i++)
        if(graf[i].x>m)
            A.pb(m-graf[i].x);
        else
            A.pb(graf[i].x);
    for(int i=m+1;i<stigao;i++)
    {
        if(graf[i].x>m)
            X.pb(m-graf[i].x);
        else
            X.pb(graf[i].x);
        if(graf[i].y>m)
            Y.pb(m-graf[i].y);
        else
            Y.pb(graf[i].y);
    }
    assert(X.size()<=n);
    answer(A,X,Y);
}

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 create_circuit(int, std::vector<int>)':
doll.cpp:137:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |     assert(X.size()<=n);
      |            ~~~~~~~~^~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7244 KB	Output is correct
2	Correct	50 ms	13552 KB	Output is correct
3	Correct	40 ms	12236 KB	Output is correct
4	Correct	6 ms	7292 KB	Output is correct
5	Correct	27 ms	10964 KB	Output is correct
6	Correct	75 ms	14792 KB	Output is correct
7	Correct	5 ms	7244 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7244 KB	Output is correct
2	Correct	50 ms	13552 KB	Output is correct
3	Correct	40 ms	12236 KB	Output is correct
4	Correct	6 ms	7292 KB	Output is correct
5	Correct	27 ms	10964 KB	Output is correct
6	Correct	75 ms	14792 KB	Output is correct
7	Correct	5 ms	7244 KB	Output is correct
8	Correct	152 ms	14340 KB	Output is correct
9	Correct	97 ms	15644 KB	Output is correct
10	Correct	145 ms	17952 KB	Output is correct
11	Correct	6 ms	7324 KB	Output is correct
12	Correct	6 ms	7244 KB	Output is correct
13	Correct	6 ms	7244 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7244 KB	Output is correct
2	Correct	50 ms	13552 KB	Output is correct
3	Correct	40 ms	12236 KB	Output is correct
4	Correct	6 ms	7292 KB	Output is correct
5	Correct	27 ms	10964 KB	Output is correct
6	Correct	75 ms	14792 KB	Output is correct
7	Correct	5 ms	7244 KB	Output is correct
8	Correct	152 ms	14340 KB	Output is correct
9	Correct	97 ms	15644 KB	Output is correct
10	Correct	145 ms	17952 KB	Output is correct
11	Correct	6 ms	7324 KB	Output is correct
12	Correct	6 ms	7244 KB	Output is correct
13	Correct	6 ms	7244 KB	Output is correct
14	Correct	152 ms	18060 KB	Output is correct
15	Correct	90 ms	12860 KB	Output is correct
16	Correct	92 ms	15664 KB	Output is correct
17	Correct	6 ms	7244 KB	Output is correct
18	Correct	7 ms	7244 KB	Output is correct
19	Correct	7 ms	7244 KB	Output is correct
20	Correct	132 ms	17736 KB	Output is correct
21	Correct	8 ms	7244 KB	Output is correct
22	Correct	7 ms	7244 KB	Output is correct