oj.uz

Submission #1060462

# Submission time Handle Problem Language Result Execution time Memory
1060462 2024-08-15T15:25:34 Z new_acc Mechanical Doll (IOI18_doll) C++14
100 / 100
 86 ms 21676 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int N=1e6+10;
int g[N][2],nw[N],val[N];
bool bb[N],usu[N];
void create_circuit(int m, vi a) {
    a.push_back(0); 
    int n=a.size(),w=1;
    while(w<n) w*=2;
    for(int i=1;i<w;i++) g[i][0]=i*2,g[i][1]=i*2+1;
    int kt=n;
    for(int i=1;i<=w;i++){
        int curr=1; 
        while(curr<w){
            bb[curr]^=1;
            curr=g[curr][bb[curr]];
        }
        int xd=2*w-curr;
        g[curr][0]=-1,g[curr][1]=-1;
        if(xd<=n){
            val[curr]=a[--kt];
            usu[curr]=0;
        }else usu[curr]=1,val[curr]=-1;
    }
    for(int i=w-1;i>=1;i--)
        if(usu[i*2] and usu[i*2+1]) usu[i]=1;
    int li=0;
    for(int i=1;i<w;i++){
        if(!usu[i]){
            nw[i]=++li;
        }
    } 
    vi c,x(li),y(li); 
    for(int i=0;i<=m;i++) c.push_back(-1);
    for(int i=1;i<w/2;i++){
        if(usu[i]) continue;
        if(usu[i*2]) x[nw[i]-1]=-1;
        else x[nw[i]-1]=-nw[g[i][0]];
        if(usu[i*2+1]) y[nw[i]-1]=-1;
        else y[nw[i]-1]=-nw[g[i][1]];
    }
    for(int i=w/2;i<w;i++){
        if(usu[i]) continue;
        x[nw[i]-1]=val[g[i][0]];
        y[nw[i]-1]=val[g[i][1]];
    }
    //for(auto u:y) cout<<u<<"\n";
    answer(c,x,y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 31 ms 9508 KB Output is correct
3 Correct 31 ms 8652 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 6 ms 3796 KB Output is correct
6 Correct 41 ms 11508 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 31 ms 9508 KB Output is correct
3 Correct 31 ms 8652 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 6 ms 3796 KB Output is correct
6 Correct 41 ms 11508 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 64 ms 15436 KB Output is correct
9 Correct 67 ms 17488 KB Output is correct
10 Correct 81 ms 21152 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 31 ms 9508 KB Output is correct
3 Correct 31 ms 8652 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 6 ms 3796 KB Output is correct
6 Correct 41 ms 11508 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 64 ms 15436 KB Output is correct
9 Correct 67 ms 17488 KB Output is correct
10 Correct 81 ms 21152 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 86 ms 20904 KB Output is correct
15 Correct 62 ms 16516 KB Output is correct
16 Correct 80 ms 20272 KB Output is correct
17 Correct 1 ms 4692 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 80 ms 19224 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 63 ms 13896 KB Output is correct
3 Correct 64 ms 13864 KB Output is correct
4 Correct 73 ms 17180 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 63 ms 13896 KB Output is correct
3 Correct 64 ms 13864 KB Output is correct
4 Correct 73 ms 17180 KB Output is correct
5 Correct 76 ms 20276 KB Output is correct
6 Correct 77 ms 21676 KB Output is correct
7 Correct 76 ms 20052 KB Output is correct
8 Correct 72 ms 19508 KB Output is correct
9 Correct 58 ms 15480 KB Output is correct
10 Correct 76 ms 19504 KB Output is correct
11 Correct 74 ms 19252 KB Output is correct
12 Correct 59 ms 15748 KB Output is correct
13 Correct 60 ms 16368 KB Output is correct
14 Correct 61 ms 16204 KB Output is correct
15 Correct 65 ms 16460 KB Output is correct
16 Correct 2 ms 4696 KB Output is correct
17 Correct 37 ms 11788 KB Output is correct
18 Correct 62 ms 13900 KB Output is correct
19 Correct 66 ms 12668 KB Output is correct
20 Correct 79 ms 16432 KB Output is correct
21 Correct 78 ms 16180 KB Output is correct
22 Correct 83 ms 16052 KB Output is correct