oj.uz

Submission #109490

# Submission time Handle Problem Language Result Execution time Memory
109490 2019-05-06T17:29:15 Z nikolapesic2802 Mechanical Doll (IOI18_doll) C++14
34 / 100
 154 ms 18092 KB 
#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,vector<int> izlazi,int skip,int sta)
{
    int ukupno=izlazi.size()+skip;
    if(ukupno==2)
    {
        if(skip)
        {
            graf[tr].x=sta;
            graf[tr].y=izlazi[0];
        }
        else
        {
            graf[tr].x=izlazi[0];
            graf[tr].y=izlazi[1];
        }
        return;
    }
    if(skip>=ukupno/2)
    {
        graf[tr].x=sta;
        graf[tr].y=stigao;
        stigao++;
        build(graf[tr].y,izlazi,skip-ukupno/2,sta);
        return;
    }
    int ss=skip;
    vector<int> levo,desno;
    for(int i=0;i<(int)izlazi.size();i++)
    {
        if(ss)
            ss--;
        else
            levo.pb(izlazi[i]),i++;
        desno.pb(izlazi[i]);
    }
    graf[tr].x=stigao;
    stigao++;
    build(graf[tr].x,levo,skip,sta);
    graf[tr].y=stigao;
    stigao++;
    build(graf[tr].y,desno,0,sta);
}
void construct(int i,vector<int> d)
{
    if(d.size()==0)
        d.pb(0);
    if(d.size()==1)
    {
        graf[i].x=d[0];
        return;
    }
    graf[i].x=stigao;
    stigao++;
    int sz=2;
    while(sz<(int)d.size())
        sz*=2;
    build(graf[i].x,d,sz-d.size(),graf[i].x);
}
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);
    int zbir=0;
    for(int i=1;i<=m;i++)
        zbir+=ide[i].size();
    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);
    }
    answer(A,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 60 ms 13524 KB Output is correct
3 Correct 45 ms 12108 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 23 ms 10948 KB Output is correct
6 Correct 73 ms 14876 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 6 ms 7244 KB Output is correct
2 Correct 60 ms 13524 KB Output is correct
3 Correct 45 ms 12108 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 23 ms 10948 KB Output is correct
6 Correct 73 ms 14876 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 78 ms 14276 KB Output is correct
9 Correct 86 ms 15596 KB Output is correct
10 Correct 130 ms 17980 KB Output is correct
11 Correct 7 ms 7244 KB Output is correct
12 Correct 6 ms 7236 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 6 ms 7244 KB Output is correct
2 Correct 60 ms 13524 KB Output is correct
3 Correct 45 ms 12108 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 23 ms 10948 KB Output is correct
6 Correct 73 ms 14876 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 78 ms 14276 KB Output is correct
9 Correct 86 ms 15596 KB Output is correct
10 Correct 130 ms 17980 KB Output is correct
11 Correct 7 ms 7244 KB Output is correct
12 Correct 6 ms 7236 KB Output is correct
13 Correct 6 ms 7244 KB Output is correct
14 Correct 144 ms 18044 KB Output is correct
15 Correct 75 ms 12860 KB Output is correct
16 Correct 112 ms 15852 KB Output is correct
17 Correct 5 ms 7244 KB Output is correct
18 Correct 6 ms 7244 KB Output is correct
19 Correct 5 ms 7244 KB Output is correct
20 Correct 109 ms 17712 KB Output is correct
21 Correct 5 ms 7244 KB Output is correct
22 Correct 6 ms 7244 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Incorrect 6 ms 7244 KB wrong motion
3 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7244 KB Output is correct
2 Correct 74 ms 12584 KB Output is correct
3 Correct 117 ms 14124 KB Output is correct
4 Correct 114 ms 15056 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7244 KB Output is correct
2 Correct 74 ms 12584 KB Output is correct
3 Correct 117 ms 14124 KB Output is correct
4 Correct 114 ms 15056 KB Output is correct
5 Partially correct 140 ms 18092 KB Output is partially correct
6 Partially correct 140 ms 17456 KB Output is partially correct
7 Partially correct 143 ms 17628 KB Output is partially correct
8 Partially correct 126 ms 16780 KB Output is partially correct
9 Partially correct 77 ms 13248 KB Output is partially correct
10 Partially correct 121 ms 16312 KB Output is partially correct
11 Partially correct 154 ms 15652 KB Output is partially correct
12 Partially correct 74 ms 12856 KB Output is partially correct
13 Partially correct 90 ms 14072 KB Output is partially correct
14 Partially correct 99 ms 14128 KB Output is partially correct
15 Partially correct 94 ms 14492 KB Output is partially correct
16 Incorrect 7 ms 7500 KB wrong motion
17 Halted 0 ms 0 KB -