oj.uz

Submission #1045599

# Submission time Handle Problem Language Result Execution time Memory
1045599 2024-08-06T06:11:24 Z happy_node Mechanical Doll (IOI18_doll) C++17
39 / 100
 64 ms 57712 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

const int MX=1e6+5, inf=1e9;

int ch[MX][2], nxt[MX], tot[MX], cnt[MX], par[MX];
bool cond[MX];

int id=1; // switch id

vector<int> G[MX];

void dfs(int v, int dep, int val, int bit, int root) {
        if(dep==1) {
                ch[v][0]= -G[root][val];
                ch[v][1]= -(G[root][val+(1<<bit)]);
                return;
        }

        if(ch[v][0]==inf) {
                ch[v][0]=id++;
        }
        dfs(ch[v][0],dep-1,val,bit+1,root);

        if(ch[v][1]==inf) {
                ch[v][1]=id++;
        }
        dfs(ch[v][1],dep-1,val+(1<<bit),bit+1,root);
}

void create_circuit(int M, std::vector<int> A) { 
        for(int i=0;i<MX;i++) {
                ch[i][0]=ch[i][1]=inf;
                nxt[i]=inf;
        }

        A.push_back(0);       
        int N=A.size();

        vector<int> C(M+1);

        C[0]=A[0];

        for(int i=0;i+1<N;i++) {
                tot[A[i]]++;
                if(nxt[A[i]]==inf) {
                        nxt[A[i]]=id++;
                        C[A[i]]= -nxt[A[i]];
                }
        }

        for(int i=0;i<=M;i++) {
                cnt[i]=tot[i];
                if(C[i]==0) {
                        C[i]=i;
                }
        }

        for(int i=N-2;i>=0;i--) {
                G[A[i]].push_back(A[i+1]);
        }

        for(int i=1;i<=M;i++) {
                if(tot[i]==0) continue;
                int b=0, c=tot[i];
                while(c>0) {
                        b++;
                        c/=2;
                }
                while(G[i].size()<(1<<b)) G[i].push_back(-nxt[i]);
                reverse(G[i].begin(),G[i].end());
                dfs(nxt[i],b,0,0,i);
        }

        vector<int> X,Y;
        for(int i=1;i<id;i++) {
                X.push_back(-ch[i][0]);
                Y.push_back(-ch[i][1]);
        }

        answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |                 while(G[i].size()<(1<<b)) G[i].push_back(-nxt[i]);
      |                       ~~~~~~~~~~~^~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42072 KB Output is correct
2 Correct 26 ms 48328 KB Output is correct
3 Correct 25 ms 48456 KB Output is correct
4 Correct 6 ms 42076 KB Output is correct
5 Correct 10 ms 43356 KB Output is correct
6 Correct 36 ms 51520 KB Output is correct
7 Correct 6 ms 42072 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42072 KB Output is correct
2 Correct 26 ms 48328 KB Output is correct
3 Correct 25 ms 48456 KB Output is correct
4 Correct 6 ms 42076 KB Output is correct
5 Correct 10 ms 43356 KB Output is correct
6 Correct 36 ms 51520 KB Output is correct
7 Correct 6 ms 42072 KB Output is correct
8 Incorrect 45 ms 51576 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42072 KB Output is correct
2 Correct 26 ms 48328 KB Output is correct
3 Correct 25 ms 48456 KB Output is correct
4 Correct 6 ms 42076 KB Output is correct
5 Correct 10 ms 43356 KB Output is correct
6 Correct 36 ms 51520 KB Output is correct
7 Correct 6 ms 42072 KB Output is correct
8 Incorrect 45 ms 51576 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 42076 KB Output is partially correct
2 Partially correct 39 ms 51388 KB Output is partially correct
3 Partially correct 45 ms 51460 KB Output is partially correct
4 Partially correct 42 ms 52800 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 42076 KB Output is partially correct
2 Partially correct 39 ms 51388 KB Output is partially correct
3 Partially correct 45 ms 51460 KB Output is partially correct
4 Partially correct 42 ms 52800 KB Output is partially correct
5 Partially correct 55 ms 54340 KB Output is partially correct
6 Partially correct 64 ms 55348 KB Output is partially correct
7 Partially correct 57 ms 55100 KB Output is partially correct
8 Partially correct 58 ms 55804 KB Output is partially correct
9 Partially correct 39 ms 52832 KB Output is partially correct
10 Partially correct 56 ms 57712 KB Output is partially correct
11 Partially correct 55 ms 57604 KB Output is partially correct
12 Partially correct 38 ms 52056 KB Output is partially correct
13 Partially correct 44 ms 50812 KB Output is partially correct
14 Partially correct 39 ms 50564 KB Output is partially correct
15 Partially correct 38 ms 50040 KB Output is partially correct
16 Partially correct 7 ms 42328 KB Output is partially correct
17 Partially correct 33 ms 50052 KB Output is partially correct
18 Partially correct 33 ms 50004 KB Output is partially correct
19 Partially correct 34 ms 50292 KB Output is partially correct
20 Partially correct 46 ms 53312 KB Output is partially correct
21 Partially correct 51 ms 55112 KB Output is partially correct
22 Partially correct 41 ms 52544 KB Output is partially correct