oj.uz

Submission #759128

# Submission time Handle Problem Language Result Execution time Memory
759128 2023-06-15T19:20:02 Z alexander707070 Mechanical Doll (IOI18_doll) C++14
37 / 100
 110 ms 37312 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(-1);
    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++){
        if(lt[i]>m or rt[i]>m)cout<<1/0;
        from.push_back(lt[i]);
        to.push_back(rt[i]);
    }

    answer(c,from,to);
}

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

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:70:38: warning: division by zero [-Wdiv-by-zero]
   70 |         if(lt[i]>m or rt[i]>m)cout<<1/0;
      |                                     ~^~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Incorrect 28 ms 23248 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Incorrect 28 ms 23248 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Incorrect 28 ms 23248 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 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 9 ms 19028 KB Output is partially correct
2 Correct 46 ms 25624 KB Output is correct
3 Partially correct 71 ms 29524 KB Output is partially correct
4 Partially correct 76 ms 30520 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 19028 KB Output is partially correct
2 Correct 46 ms 25624 KB Output is correct
3 Partially correct 71 ms 29524 KB Output is partially correct
4 Partially correct 76 ms 30520 KB Output is partially correct
5 Partially correct 86 ms 34164 KB Output is partially correct
6 Partially correct 91 ms 35668 KB Output is partially correct
7 Partially correct 90 ms 35092 KB Output is partially correct
8 Partially correct 93 ms 36516 KB Output is partially correct
9 Partially correct 70 ms 30660 KB Output is partially correct
10 Partially correct 110 ms 36936 KB Output is partially correct
11 Partially correct 98 ms 37312 KB Output is partially correct
12 Partially correct 67 ms 31024 KB Output is partially correct
13 Partially correct 67 ms 30104 KB Output is partially correct
14 Partially correct 61 ms 29488 KB Output is partially correct
15 Partially correct 59 ms 28904 KB Output is partially correct
16 Partially correct 11 ms 19432 KB Output is partially correct
17 Partially correct 60 ms 28396 KB Output is partially correct
18 Partially correct 57 ms 28400 KB Output is partially correct
19 Partially correct 60 ms 29172 KB Output is partially correct
20 Partially correct 83 ms 31896 KB Output is partially correct
21 Partially correct 90 ms 34832 KB Output is partially correct
22 Partially correct 73 ms 31124 KB Output is partially correct