oj.uz

Submission #759130

# Submission time Handle Problem Language Result Execution time Memory
759130 2023-06-15T19:22:16 Z alexander707070 Mechanical Doll (IOI18_doll) C++14
37 / 100
 108 ms 37284 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]<-curr or rt[i]<-curr)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:46: warning: division by zero [-Wdiv-by-zero]
   70 |         if(lt[i]<-curr or rt[i]<-curr)cout<<1/0;
      |                                             ~^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 30 ms 23180 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 10 ms 19024 KB Output is partially correct
2 Correct 48 ms 25648 KB Output is correct
3 Partially correct 81 ms 29604 KB Output is partially correct
4 Partially correct 88 ms 30532 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 19024 KB Output is partially correct
2 Correct 48 ms 25648 KB Output is correct
3 Partially correct 81 ms 29604 KB Output is partially correct
4 Partially correct 88 ms 30532 KB Output is partially correct
5 Partially correct 85 ms 34052 KB Output is partially correct
6 Partially correct 96 ms 35704 KB Output is partially correct
7 Partially correct 94 ms 35184 KB Output is partially correct
8 Partially correct 92 ms 36536 KB Output is partially correct
9 Partially correct 78 ms 30556 KB Output is partially correct
10 Partially correct 99 ms 36992 KB Output is partially correct
11 Partially correct 100 ms 37284 KB Output is partially correct
12 Partially correct 72 ms 31004 KB Output is partially correct
13 Partially correct 67 ms 29984 KB Output is partially correct
14 Partially correct 70 ms 29508 KB Output is partially correct
15 Partially correct 60 ms 28920 KB Output is partially correct
16 Partially correct 11 ms 19412 KB Output is partially correct
17 Partially correct 55 ms 28352 KB Output is partially correct
18 Partially correct 56 ms 28420 KB Output is partially correct
19 Partially correct 58 ms 29132 KB Output is partially correct
20 Partially correct 88 ms 32016 KB Output is partially correct
21 Partially correct 108 ms 34840 KB Output is partially correct
22 Partially correct 69 ms 31048 KB Output is partially correct