oj.uz

Submission #760833

# Submission time Handle Problem Language Result Execution time Memory
760833 2023-06-18T16:24:59 Z alexander707070 Mechanical Doll (IOI18_doll) C++14
50.6729 / 100
 223 ms 12832 KB 
#include<bits/stdc++.h>
#include "doll.h"
#define MAXN 800007
using namespace std;
 
int m,power,n,num;
int a[MAXN],s,ind[MAXN],temp[MAXN];
int lt[MAXN],rt[MAXN];
vector<int> from,to,c;

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){
    if(l>=n and r<power-1){
        lt[v]=rt[v]=-1;
        return;
    }

    if(l+1==r){
        if(l<n)lt[v]=a[l];
        else lt[v]=-1;

        if(r<n)rt[v]=a[r];
        else if(r==power-1)rt[v]=0;
        else rt[v]=-1;
    }else{
        int tt=(l+r)/2;
        num++; lt[v]=-num;
        build(num,l,tt);
        num++; rt[v]=-num;
        build(num,tt+1,r);
    }
}

bool cmp(int x,int y){
    return rev(x)<rev(y);
}
 
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]; ind[i]=i;
    }

    power=1; num=1;
    while(power<n+1)power*=2;

    sort(ind,ind+n,cmp);

    for(int i=0;i<n;i++)temp[ind[i]]=a[i];
    for(int i=0;i<n;i++)a[i]=temp[i];

    build(1,0,power-1);
 
    for(int i=0;i<=m;i++)c.push_back(-1);
 
    for(int i=1;i<=num;i++){
        from.push_back(lt[i]);
        to.push_back(rt[i]);
    }
    answer(c,from,to);
}
 
/*
int main(){
     create_circuit(4, {1, 2, 1,3,2,4,3,1,2});
}
*/

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
12.3258440412 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Output is partially correct
2 Partially correct 174 ms 8524 KB Output is partially correct
3 Partially correct 154 ms 8528 KB Output is partially correct
4 Partially correct 223 ms 12196 KB Output is partially correct

Subtask #6
38.3470703504 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Output is partially correct
2 Partially correct 174 ms 8524 KB Output is partially correct
3 Partially correct 154 ms 8528 KB Output is partially correct
4 Partially correct 223 ms 12196 KB Output is partially correct
5 Partially correct 223 ms 12832 KB Output is partially correct
6 Partially correct 216 ms 12528 KB Output is partially correct
7 Partially correct 221 ms 12664 KB Output is partially correct
8 Partially correct 212 ms 12364 KB Output is partially correct
9 Partially correct 179 ms 8532 KB Output is partially correct
10 Partially correct 216 ms 12384 KB Output is partially correct
11 Partially correct 211 ms 12120 KB Output is partially correct
12 Partially correct 152 ms 8832 KB Output is partially correct
13 Partially correct 179 ms 9268 KB Output is partially correct
14 Partially correct 155 ms 9292 KB Output is partially correct
15 Partially correct 160 ms 9568 KB Output is partially correct
16 Partially correct 5 ms 596 KB Output is partially correct
17 Correct 173 ms 8084 KB Output is correct
18 Partially correct 177 ms 8804 KB Output is partially correct
19 Partially correct 157 ms 8760 KB Output is partially correct
20 Partially correct 215 ms 12252 KB Output is partially correct
21 Partially correct 222 ms 12112 KB Output is partially correct
22 Partially correct 219 ms 12108 KB Output is partially correct