oj.uz

Submission #713863

# Submission time Handle Problem Language Result Execution time Memory
713863 2023-03-23T06:30:07 Z victor_gao Mechanical Doll (IOI18_doll) C++17
53 / 100
 111 ms 22508 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>to[100015],g[100015];
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
*/

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 4 ms 8148 KB Output is correct
2 Correct 36 ms 14092 KB Output is correct
3 Correct 27 ms 13840 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 13 ms 9300 KB Output is correct
6 Correct 41 ms 16864 KB Output is correct
7 Correct 5 ms 8020 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 36 ms 14092 KB Output is correct
3 Correct 27 ms 13840 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 13 ms 9300 KB Output is correct
6 Correct 41 ms 16864 KB Output is correct
7 Correct 5 ms 8020 KB Output is correct
8 Correct 54 ms 16988 KB Output is correct
9 Correct 65 ms 17788 KB Output is correct
10 Correct 82 ms 21032 KB Output is correct
11 Correct 5 ms 8020 KB Output is correct
12 Correct 5 ms 8072 KB Output is correct
13 Correct 5 ms 8072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 36 ms 14092 KB Output is correct
3 Correct 27 ms 13840 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 13 ms 9300 KB Output is correct
6 Correct 41 ms 16864 KB Output is correct
7 Correct 5 ms 8020 KB Output is correct
8 Correct 54 ms 16988 KB Output is correct
9 Correct 65 ms 17788 KB Output is correct
10 Correct 82 ms 21032 KB Output is correct
11 Correct 5 ms 8020 KB Output is correct
12 Correct 5 ms 8072 KB Output is correct
13 Correct 5 ms 8072 KB Output is correct
14 Correct 91 ms 20404 KB Output is correct
15 Correct 48 ms 15184 KB Output is correct
16 Correct 74 ms 17452 KB Output is correct
17 Correct 5 ms 8020 KB Output is correct
18 Correct 5 ms 8148 KB Output is correct
19 Correct 4 ms 8020 KB Output is correct
20 Correct 86 ms 19912 KB Output is correct
21 Correct 4 ms 8020 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8072 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 4 ms 8148 KB Output is partially correct
2 Correct 50 ms 15016 KB Output is correct
3 Partially correct 74 ms 17276 KB Output is partially correct
4 Partially correct 81 ms 17900 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 8148 KB Output is partially correct
2 Correct 50 ms 15016 KB Output is correct
3 Partially correct 74 ms 17276 KB Output is partially correct
4 Partially correct 81 ms 17900 KB Output is partially correct
5 Partially correct 98 ms 21176 KB Output is partially correct
6 Partially correct 111 ms 21836 KB Output is partially correct
7 Partially correct 103 ms 21364 KB Output is partially correct
8 Partially correct 103 ms 22220 KB Output is partially correct
9 Partially correct 71 ms 17328 KB Output is partially correct
10 Partially correct 104 ms 21816 KB Output is partially correct
11 Partially correct 102 ms 22508 KB Output is partially correct
12 Partially correct 73 ms 17768 KB Output is partially correct
13 Partially correct 69 ms 17140 KB Output is partially correct
14 Partially correct 64 ms 16812 KB Output is partially correct
15 Partially correct 70 ms 16720 KB Output is partially correct
16 Partially correct 6 ms 8408 KB Output is partially correct
17 Partially correct 56 ms 15956 KB Output is partially correct
18 Partially correct 58 ms 15944 KB Output is partially correct
19 Partially correct 65 ms 16512 KB Output is partially correct
20 Partially correct 84 ms 18768 KB Output is partially correct
21 Partially correct 92 ms 20948 KB Output is partially correct
22 Partially correct 79 ms 18292 KB Output is partially correct