oj.uz

Submission #759131

# Submission time Handle Problem Language Result Execution time Memory
759131 2023-06-15T19:23:30 Z alexander707070 Mechanical Doll (IOI18_doll) C++14
53 / 100
 116 ms 37316 KB 
#include<bits/stdc++.h>
#include "doll.h"
#define MAXN 800007
using namespace std;

int m,power,n,sz,curr,root;
int a[MAXN],s;
int lt[MAXN],rt[MAXN];
vector<int> from,to,c,w[MAXN];

int rev(int x){
    int res=0;
    for(int i=1;i<power;i*=2){
        res*=2; res+=x%2; 
        x/=2;
    }
    return res;
}

void build(int v,int l,int r,int num,int id){
    if(l+1==r){
        num*=2;
        if(rev(num)<sz-1)lt[v]=w[id][rev(num)];
        else if(rev(num)==power-1)lt[v]=w[id].back();
        else lt[v]=-root;

        num++;
        if(rev(num)<sz-1)rt[v]=w[id][rev(num)];
        else if(rev(num)==power-1)rt[v]=w[id].back();
        else rt[v]=-root;

    }else{
        int tt=(l+r)/2;
        curr++; lt[v]=-curr;
        build(curr,l,tt,2*num,id);
        curr++; rt[v]=-curr;
        build(curr,tt+1,r,2*num+1,id);
    }
}

void create_circuit(int M, vector<int> A){
    m=M; n=int(A.size());

    for(int i=0;i<n;i++){
        a[i]=A[i];
    }

    for(int i=0;i<n;i++){
        w[a[i]].push_back(a[i+1]);
    }

    for(int i=0;i<=m;i++)c.push_back(0);
    c[0]=a[0];

    for(int i=1;i<=m;i++){
        if(w[i].empty())continue;

        if(w[i].size()==1){
            c[i]=w[i][0]; continue;
        }

        sz=w[i].size(); power=1;
        while(power<sz)power*=2;

        curr++; root=curr; c[i]=-root;
        build(curr,0,power-1,0,i);
    }

    for(int i=1;i<=curr;i++){
        from.push_back(lt[i]);
        to.push_back(rt[i]);
    }

    answer(c,from,to);
}

/*
int main(){
     create_circuit(4, {1,2,1,3});
}
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 29 ms 23208 KB Output is correct
3 Correct 25 ms 22796 KB Output is correct
4 Correct 9 ms 19100 KB Output is correct
5 Correct 18 ms 20296 KB Output is correct
6 Correct 33 ms 24724 KB Output is correct
7 Correct 13 ms 19028 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 29 ms 23208 KB Output is correct
3 Correct 25 ms 22796 KB Output is correct
4 Correct 9 ms 19100 KB Output is correct
5 Correct 18 ms 20296 KB Output is correct
6 Correct 33 ms 24724 KB Output is correct
7 Correct 13 ms 19028 KB Output is correct
8 Correct 43 ms 26272 KB Output is correct
9 Correct 48 ms 26964 KB Output is correct
10 Correct 77 ms 30852 KB Output is correct
11 Correct 9 ms 19028 KB Output is correct
12 Correct 10 ms 19008 KB Output is correct
13 Correct 9 ms 19028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 29 ms 23208 KB Output is correct
3 Correct 25 ms 22796 KB Output is correct
4 Correct 9 ms 19100 KB Output is correct
5 Correct 18 ms 20296 KB Output is correct
6 Correct 33 ms 24724 KB Output is correct
7 Correct 13 ms 19028 KB Output is correct
8 Correct 43 ms 26272 KB Output is correct
9 Correct 48 ms 26964 KB Output is correct
10 Correct 77 ms 30852 KB Output is correct
11 Correct 9 ms 19028 KB Output is correct
12 Correct 10 ms 19008 KB Output is correct
13 Correct 9 ms 19028 KB Output is correct
14 Correct 72 ms 33584 KB Output is correct
15 Correct 43 ms 26108 KB Output is correct
16 Correct 64 ms 30124 KB Output is correct
17 Correct 9 ms 19028 KB Output is correct
18 Correct 9 ms 19028 KB Output is correct
19 Correct 9 ms 19028 KB Output is correct
20 Correct 67 ms 32188 KB Output is correct
21 Correct 10 ms 19032 KB Output is correct
22 Correct 9 ms 19108 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 19028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 19120 KB Output is partially correct
2 Correct 44 ms 25576 KB Output is correct
3 Partially correct 69 ms 29516 KB Output is partially correct
4 Partially correct 77 ms 30572 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 19120 KB Output is partially correct
2 Correct 44 ms 25576 KB Output is correct
3 Partially correct 69 ms 29516 KB Output is partially correct
4 Partially correct 77 ms 30572 KB Output is partially correct
5 Partially correct 86 ms 34164 KB Output is partially correct
6 Partially correct 93 ms 35656 KB Output is partially correct
7 Partially correct 90 ms 35096 KB Output is partially correct
8 Partially correct 92 ms 36572 KB Output is partially correct
9 Partially correct 87 ms 30584 KB Output is partially correct
10 Partially correct 98 ms 37024 KB Output is partially correct
11 Partially correct 116 ms 37316 KB Output is partially correct
12 Partially correct 74 ms 30972 KB Output is partially correct
13 Partially correct 69 ms 29928 KB Output is partially correct
14 Partially correct 62 ms 29536 KB Output is partially correct
15 Partially correct 70 ms 28856 KB Output is partially correct
16 Partially correct 12 ms 19412 KB Output is partially correct
17 Partially correct 57 ms 28372 KB Output is partially correct
18 Partially correct 59 ms 28444 KB Output is partially correct
19 Partially correct 59 ms 29208 KB Output is partially correct
20 Partially correct 89 ms 32004 KB Output is partially correct
21 Partially correct 87 ms 34888 KB Output is partially correct
22 Partially correct 76 ms 31124 KB Output is partially correct