oj.uz

Submission #713782

# Submission time Handle Problem Language Result Execution time Memory
713782 2023-03-23T03:48:55 Z alvingogo Mechanical Doll (IOI18_doll) C++14
84 / 100
 137 ms 12192 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();
    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 3 ms 4948 KB Output is correct
2 Correct 43 ms 8216 KB Output is correct
3 Correct 40 ms 8108 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 12 ms 6100 KB Output is correct
6 Correct 53 ms 9632 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 3 ms 4948 KB Output is correct
2 Correct 43 ms 8216 KB Output is correct
3 Correct 40 ms 8108 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 12 ms 6100 KB Output is correct
6 Correct 53 ms 9632 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 3 ms 4948 KB Output is correct
2 Correct 43 ms 8216 KB Output is correct
3 Correct 40 ms 8108 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 12 ms 6100 KB Output is correct
6 Correct 53 ms 9632 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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 4884 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 2 ms 4948 KB Output is correct
2 Correct 62 ms 8868 KB Output is correct
3 Correct 65 ms 8872 KB Output is correct
4 Correct 96 ms 10780 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 62 ms 8868 KB Output is correct
3 Correct 65 ms 8872 KB Output is correct
4 Correct 96 ms 10780 KB Output is correct
5 Correct 133 ms 12192 KB Output is correct
6 Correct 123 ms 11772 KB Output is correct
7 Correct 137 ms 11928 KB Output is correct
8 Correct 96 ms 11612 KB Output is correct
9 Correct 71 ms 8896 KB Output is correct
10 Correct 104 ms 11588 KB Output is correct
11 Correct 92 ms 11200 KB Output is correct
12 Correct 68 ms 9124 KB Output is correct
13 Correct 71 ms 9400 KB Output is correct
14 Correct 71 ms 9604 KB Output is correct
15 Correct 69 ms 9736 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 62 ms 9136 KB Output is correct
18 Correct 84 ms 9000 KB Output is correct
19 Correct 70 ms 9128 KB Output is correct
20 Correct 98 ms 11444 KB Output is correct
21 Correct 108 ms 11172 KB Output is correct
22 Correct 105 ms 11244 KB Output is correct