oj.uz

Submission #713784

# Submission time Handle Problem Language Result Execution time Memory
713784 2023-03-23T03:53:17 Z alvingogo Mechanical Doll (IOI18_doll) C++14
100 / 100
 126 ms 13056 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==2){
        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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 40 ms 8252 KB Output is correct
3 Correct 40 ms 8084 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 56 ms 9640 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 40 ms 8252 KB Output is correct
3 Correct 40 ms 8084 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 56 ms 9640 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 72 ms 10272 KB Output is correct
9 Correct 73 ms 10868 KB Output is correct
10 Correct 108 ms 13056 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 40 ms 8252 KB Output is correct
3 Correct 40 ms 8084 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 56 ms 9640 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 72 ms 10272 KB Output is correct
9 Correct 73 ms 10868 KB Output is correct
10 Correct 108 ms 13056 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 107 ms 12572 KB Output is correct
15 Correct 67 ms 9828 KB Output is correct
16 Correct 101 ms 12332 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 126 ms 12764 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 5 ms 4948 KB Output is correct
3 Correct 5 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 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 71 ms 8824 KB Output is correct
3 Correct 86 ms 8884 KB Output is correct
4 Correct 99 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 71 ms 8824 KB Output is correct
3 Correct 86 ms 8884 KB Output is correct
4 Correct 99 ms 10792 KB Output is correct
5 Correct 99 ms 12092 KB Output is correct
6 Correct 101 ms 11820 KB Output is correct
7 Correct 101 ms 11908 KB Output is correct
8 Correct 101 ms 11564 KB Output is correct
9 Correct 61 ms 8852 KB Output is correct
10 Correct 98 ms 11544 KB Output is correct
11 Correct 97 ms 11176 KB Output is correct
12 Correct 64 ms 9028 KB Output is correct
13 Correct 66 ms 9440 KB Output is correct
14 Correct 73 ms 9556 KB Output is correct
15 Correct 67 ms 9736 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 62 ms 9108 KB Output is correct
18 Correct 63 ms 9000 KB Output is correct
19 Correct 63 ms 9032 KB Output is correct
20 Correct 96 ms 11424 KB Output is correct
21 Correct 102 ms 11212 KB Output is correct
22 Correct 99 ms 11180 KB Output is correct