oj.uz

Submission #713783

# Submission time Handle Problem Language Result Execution time Memory
713783 2023-03-23T03:52:36 Z alvingogo Mechanical Doll (IOI18_doll) C++14
84 / 100
 113 ms 12188 KB 
#include <bits/stdc++.h>
#include "doll.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<int> g,x,y;
int nw=0;
vector<pair<int,int> > v;
vector<int> tp;
const int inf=1e9;
int build(int f,int sz){
    queue<int> q;
    q.push(f);
    int cnt=0;
    while(cnt<sz/2-1){
        auto h=q.front();
        q.pop();
        x[h]=f+1;
        y[h]=f+2;
        q.push(f+1);
        q.push(f+2);
        f+=2;
        cnt++;
    }
    return f+1;
}
void go(int z){
    int root=0;
    while(1){
        if(tp[root]==0){
            tp[root]=1;
            if(x[root]==-1){
                x[root]=inf+z;
                break;
            }
            root=x[root];
        }
        else{
            tp[root]=0;
            if(y[root]==-1){
                y[root]=inf+z;
                break;
            }
            root=y[root];
        }
    }
}
void create_circuit(int m, vector<int> a) {
    a.push_back(0);
    int n=a.size();
    if(n==1){
        vector<int> d,e,f;
        d.resize(m+1,0);
        d[0]=a[0];
        answer(d,e,f);
        return;
    }
    g.clear();
    g.resize(m+1,-1);
    int root=0;
    x.resize(400000,-1);
    y.resize(400000,-1);
    tp.resize(400000,0);
    int flag=0;
    for(int i=(1<<19);i>1;i>>=1){
        if(n>=i){
            flag=1;
            n-=i;
            int c=root+1;
            y[root]=c;
            int u=build(c,i);
            if(n==0){
                x[root]=0;
                root=u-1;
                break;
            }
            x[root]=u;
            root=u;
        }
        else{
            if(!flag || !n){
                continue;
            }
            x[root]=0;
            y[root]=root+1;
            root++;
        }
    }
    if(n%2){
        x[root]=0;
    }
    x.resize(root+1);
    y.resize(root+1);
    n=a.size();
    for(int i=0;i<n;i++){
        go(a[i]);
    }
    for(int i=0;i<=root;i++){
        if(x[i]>=inf){
            x[i]-=inf;
        }
        else{
            x[i]=-1-(x[i]);
        }
        if(y[i]>=inf){
            y[i]-=inf;
        }
        else{
            y[i]=-1-(y[i]);
        }
    }
    answer(g,x,y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 39 ms 8228 KB Output is correct
3 Correct 36 ms 8136 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 55 ms 9636 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 39 ms 8228 KB Output is correct
3 Correct 36 ms 8136 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 55 ms 9636 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 39 ms 8228 KB Output is correct
3 Correct 36 ms 8136 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 55 ms 9636 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 62 ms 8856 KB Output is correct
3 Correct 69 ms 8880 KB Output is correct
4 Correct 96 ms 10792 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 62 ms 8856 KB Output is correct
3 Correct 69 ms 8880 KB Output is correct
4 Correct 96 ms 10792 KB Output is correct
5 Correct 103 ms 12188 KB Output is correct
6 Correct 100 ms 11944 KB Output is correct
7 Correct 98 ms 11932 KB Output is correct
8 Correct 113 ms 11568 KB Output is correct
9 Correct 66 ms 8840 KB Output is correct
10 Correct 99 ms 11460 KB Output is correct
11 Correct 94 ms 11196 KB Output is correct
12 Correct 63 ms 9132 KB Output is correct
13 Correct 67 ms 9440 KB Output is correct
14 Correct 67 ms 9592 KB Output is correct
15 Correct 65 ms 9748 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 63 ms 9068 KB Output is correct
18 Correct 63 ms 9060 KB Output is correct
19 Correct 62 ms 9116 KB Output is correct
20 Correct 96 ms 11360 KB Output is correct
21 Correct 98 ms 11180 KB Output is correct
22 Correct 99 ms 11172 KB Output is correct