oj.uz

Submission #109500

# Submission time Handle Problem Language Result Execution time Memory
109500 2019-05-06T18:14:27 Z nikolapesic2802 Mechanical Doll (IOI18_doll) C++14
100 / 100
 207 ms 19680 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);
vector<int> skips;
int stigao;
void markskips(vector<int> poz,int koliko)
{
    if(koliko==0)
        return;
    vector<int> levo,desno;
    for(int i=0;i<(int)poz.size();i++)
        if(i%2)
            desno.pb(poz[i]);
        else
            levo.pb(poz[i]);
    if((int)levo.size()<=koliko)
        for(auto p:levo)
            skips[p]=1;
    else
        markskips(levo,koliko);
    if((int)levo.size()<koliko)
        markskips(desno,koliko-(int)levo.size());
}
void build(int tr,vector<int> izlazi,int skip,int sta)
{
    int ukupno=izlazi.size()+skip;
    assert(ukupno%2==0);
    if(ukupno==2)
    {
        if(skip)
        {
            assert(skip==1);
            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;
    }
    skips.resize(ukupno);
    fill(all(skips),0);
    vector<int> pozicije;
    for(int i=0;i<ukupno;i++)
        pozicije.pb(i);
    markskips(pozicije,skip);
    vector<int> levo,desno;
    int trr=0;
    for(int i=0;i<ukupno;i++)
    {
        if(i%2)
            desno.pb(izlazi[trr++]),assert(!skips[i]);
        else
            if(!skips[i])
                levo.pb(izlazi[trr++]);
    }
    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 create_circuit(int m, vector<int> a)
{
    a.pb(0);
    stigao=m+1;
    for(int i=0;i<=m;i++)
        graf[i].x=stigao;
    stigao++;
    int sz=2;
    while(sz<(int)a.size())
        sz*=2;
    build(stigao-1,a,sz-a.size(),stigao-1);
    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);
    }
    answer(A,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7244 KB Output is correct
2 Correct 74 ms 12520 KB Output is correct
3 Correct 62 ms 12216 KB Output is correct
4 Correct 6 ms 7272 KB Output is correct
5 Correct 19 ms 8624 KB Output is correct
6 Correct 92 ms 14512 KB Output is correct
7 Correct 8 ms 7244 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7244 KB Output is correct
2 Correct 74 ms 12520 KB Output is correct
3 Correct 62 ms 12216 KB Output is correct
4 Correct 6 ms 7272 KB Output is correct
5 Correct 19 ms 8624 KB Output is correct
6 Correct 92 ms 14512 KB Output is correct
7 Correct 8 ms 7244 KB Output is correct
8 Correct 126 ms 15796 KB Output is correct
9 Correct 115 ms 16580 KB Output is correct
10 Correct 176 ms 19680 KB Output is correct
11 Correct 6 ms 7244 KB Output is correct
12 Correct 6 ms 7244 KB Output is correct
13 Correct 7 ms 7244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7244 KB Output is correct
2 Correct 74 ms 12520 KB Output is correct
3 Correct 62 ms 12216 KB Output is correct
4 Correct 6 ms 7272 KB Output is correct
5 Correct 19 ms 8624 KB Output is correct
6 Correct 92 ms 14512 KB Output is correct
7 Correct 8 ms 7244 KB Output is correct
8 Correct 126 ms 15796 KB Output is correct
9 Correct 115 ms 16580 KB Output is correct
10 Correct 176 ms 19680 KB Output is correct
11 Correct 6 ms 7244 KB Output is correct
12 Correct 6 ms 7244 KB Output is correct
13 Correct 7 ms 7244 KB Output is correct
14 Correct 161 ms 19232 KB Output is correct
15 Correct 115 ms 15792 KB Output is correct
16 Correct 157 ms 19148 KB Output is correct
17 Correct 5 ms 7244 KB Output is correct
18 Correct 6 ms 7284 KB Output is correct
19 Correct 6 ms 7244 KB Output is correct
20 Correct 167 ms 19212 KB Output is correct
21 Correct 6 ms 7244 KB Output is correct
22 Correct 6 ms 7352 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 11 ms 7244 KB Output is correct
3 Correct 6 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 7 ms 7288 KB Output is correct
7 Correct 6 ms 7256 KB Output is correct
8 Correct 5 ms 7244 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 158 ms 15020 KB Output is correct
3 Correct 147 ms 14916 KB Output is correct
4 Correct 156 ms 18184 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 158 ms 15020 KB Output is correct
3 Correct 147 ms 14916 KB Output is correct
4 Correct 156 ms 18184 KB Output is correct
5 Correct 162 ms 19036 KB Output is correct
6 Correct 161 ms 19044 KB Output is correct
7 Correct 207 ms 19084 KB Output is correct
8 Correct 179 ms 18840 KB Output is correct
9 Correct 117 ms 15000 KB Output is correct
10 Correct 206 ms 18772 KB Output is correct
11 Correct 165 ms 17816 KB Output is correct
12 Correct 108 ms 15348 KB Output is correct
13 Correct 112 ms 15676 KB Output is correct
14 Correct 108 ms 15640 KB Output is correct
15 Correct 117 ms 15720 KB Output is correct
16 Correct 10 ms 7588 KB Output is correct
17 Correct 119 ms 13880 KB Output is correct
18 Correct 101 ms 15028 KB Output is correct
19 Correct 135 ms 15360 KB Output is correct
20 Correct 167 ms 18820 KB Output is correct
21 Correct 184 ms 18556 KB Output is correct
22 Correct 156 ms 18644 KB Output is correct