oj.uz

Submission #713871

# Submission time Handle Problem Language Result Execution time Memory
713871 2023-03-23T06:36:05 Z victor_gao Mechanical Doll (IOI18_doll) C++17
53 / 100
 117 ms 26972 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>to[200015],g[200015];
vector<int>ans1,ans2,c;
int n,m,now=0;
int build(int num,int l,int r,int root){
    if (l==r){
        if (g[num][l]==-1) return -root;
        else return -g[num][l];
    }
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    int p1=build(num,l,mid,root);
    ans1[use]=-p1;
    int p2=build(num,mid+1,r,root);
    ans2[use]=-p2;
    return use;
}
void create_circuit(int M, std::vector<int> A) {
    m=M;
    ans1.resize(400000); ans2.resize(400000);
    A.push_back(0);
    n = A.size();
    for (int i=0;i<n-1;i++){
        to[A[i]].push_back(A[i+1]);
    }
    for (int i=1;i<=m;i++){
        if (to[i].empty()) continue;
        int p=0;
        for (int j=0; ;j++){
            if ((1LL<<j)>=(int)to[i].size()){
                p=j;
                break;
            }
        }
        g[i].resize((1LL<<p),-1);
        for (int j=0;j<to[i].size();j++){
            int idx=0;
            for (int k=0;k<p;k++){
                if (j&(1LL<<k))
                    idx=(idx+(1LL<<(p-k-1)));
            }
            if (j==to[i].size()-1)
                g[i][(1LL<<p)-1]=to[i][j];
            else g[i][idx]=to[i][j];
        }
    }
    c.resize(m+1);
    for (int i=0;i<=m;i++){
        if (g[i].empty()) c[i]=0;
        else if (g[i].size()==1) c[i]=g[i][0];
        else c[i]=-build(i,0,g[i].size()-1,now-1);
    }
    c[0]=A[0];
    now=abs(now);
    vector<int>X,Y;
    for (int i=1;i<=now;i++){
        X.push_back(ans1[i]);
    }
    for (int i=1;i<=now;i++){
        Y.push_back(ans2[i]);
    }
    answer(c, X, Y);
}
/*
2 16
1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 2 1
./rand
./doll
*/

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j=0;j<to[i].size();j++){
      |                      ~^~~~~~~~~~~~~
doll.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (j==to[i].size()-1)
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 37 ms 18500 KB Output is correct
3 Correct 42 ms 18268 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 16 ms 13908 KB Output is correct
6 Correct 47 ms 21176 KB Output is correct
7 Correct 6 ms 12836 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 37 ms 18500 KB Output is correct
3 Correct 42 ms 18268 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 16 ms 13908 KB Output is correct
6 Correct 47 ms 21176 KB Output is correct
7 Correct 6 ms 12836 KB Output is correct
8 Correct 53 ms 21172 KB Output is correct
9 Correct 53 ms 22096 KB Output is correct
10 Correct 75 ms 25316 KB Output is correct
11 Correct 8 ms 12832 KB Output is correct
12 Correct 7 ms 12780 KB Output is correct
13 Correct 7 ms 12792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 37 ms 18500 KB Output is correct
3 Correct 42 ms 18268 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 16 ms 13908 KB Output is correct
6 Correct 47 ms 21176 KB Output is correct
7 Correct 6 ms 12836 KB Output is correct
8 Correct 53 ms 21172 KB Output is correct
9 Correct 53 ms 22096 KB Output is correct
10 Correct 75 ms 25316 KB Output is correct
11 Correct 8 ms 12832 KB Output is correct
12 Correct 7 ms 12780 KB Output is correct
13 Correct 7 ms 12792 KB Output is correct
14 Correct 90 ms 24884 KB Output is correct
15 Correct 48 ms 19548 KB Output is correct
16 Correct 76 ms 21900 KB Output is correct
17 Correct 7 ms 12804 KB Output is correct
18 Correct 7 ms 12756 KB Output is correct
19 Correct 7 ms 12756 KB Output is correct
20 Correct 85 ms 24196 KB Output is correct
21 Correct 7 ms 12756 KB Output is correct
22 Correct 6 ms 12756 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12756 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 8 ms 12960 KB Output is partially correct
2 Correct 51 ms 19348 KB Output is correct
3 Partially correct 75 ms 21700 KB Output is partially correct
4 Partially correct 95 ms 22372 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 12960 KB Output is partially correct
2 Correct 51 ms 19348 KB Output is correct
3 Partially correct 75 ms 21700 KB Output is partially correct
4 Partially correct 95 ms 22372 KB Output is partially correct
5 Partially correct 97 ms 25528 KB Output is partially correct
6 Partially correct 109 ms 26184 KB Output is partially correct
7 Partially correct 117 ms 25860 KB Output is partially correct
8 Partially correct 107 ms 26596 KB Output is partially correct
9 Partially correct 72 ms 21732 KB Output is partially correct
10 Partially correct 108 ms 26196 KB Output is partially correct
11 Partially correct 105 ms 26972 KB Output is partially correct
12 Partially correct 78 ms 22112 KB Output is partially correct
13 Partially correct 78 ms 21592 KB Output is partially correct
14 Partially correct 73 ms 21352 KB Output is partially correct
15 Partially correct 64 ms 21072 KB Output is partially correct
16 Partially correct 8 ms 13012 KB Output is partially correct
17 Partially correct 59 ms 20328 KB Output is partially correct
18 Partially correct 60 ms 20296 KB Output is partially correct
19 Partially correct 62 ms 20836 KB Output is partially correct
20 Partially correct 83 ms 23108 KB Output is partially correct
21 Partially correct 96 ms 25308 KB Output is partially correct
22 Partially correct 76 ms 22460 KB Output is partially correct