oj.uz

Submission #1045613

# Submission time Handle Problem Language Result Execution time Memory
1045613 2024-08-06T06:24:22 Z happy_node Mechanical Doll (IOI18_doll) C++17
39 / 100
 61 ms 56124 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]]++;
        }

        for(int i=1;i<=M;i++) {
                cnt[i]=tot[i];
                if(tot[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;

                if(tot[i]==1) {
                        C[i]=G[i][0];
                        continue;
                }

                nxt[i]=id++;
                C[i]=-nxt[i];

                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]);
        }

        assert(X.size()<=400'000);

        answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:77:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |                 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 5 ms 42072 KB Output is correct
2 Correct 18 ms 45912 KB Output is correct
3 Correct 16 ms 45652 KB Output is correct
4 Correct 6 ms 42076 KB Output is correct
5 Correct 12 ms 43356 KB Output is correct
6 Correct 23 ms 47424 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 5 ms 42072 KB Output is correct
2 Correct 18 ms 45912 KB Output is correct
3 Correct 16 ms 45652 KB Output is correct
4 Correct 6 ms 42076 KB Output is correct
5 Correct 12 ms 43356 KB Output is correct
6 Correct 23 ms 47424 KB Output is correct
7 Correct 6 ms 42072 KB Output is correct
8 Incorrect 42 ms 50660 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 42072 KB Output is correct
2 Correct 18 ms 45912 KB Output is correct
3 Correct 16 ms 45652 KB Output is correct
4 Correct 6 ms 42076 KB Output is correct
5 Correct 12 ms 43356 KB Output is correct
6 Correct 23 ms 47424 KB Output is correct
7 Correct 6 ms 42072 KB Output is correct
8 Incorrect 42 ms 50660 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 42072 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 37 ms 50440 KB Output is partially correct
3 Partially correct 38 ms 50436 KB Output is partially correct
4 Partially correct 43 ms 51276 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 37 ms 50440 KB Output is partially correct
3 Partially correct 38 ms 50436 KB Output is partially correct
4 Partially correct 43 ms 51276 KB Output is partially correct
5 Partially correct 55 ms 53072 KB Output is partially correct
6 Partially correct 58 ms 53884 KB Output is partially correct
7 Partially correct 57 ms 53680 KB Output is partially correct
8 Partially correct 61 ms 54368 KB Output is partially correct
9 Partially correct 38 ms 51800 KB Output is partially correct
10 Partially correct 56 ms 56116 KB Output is partially correct
11 Partially correct 56 ms 56124 KB Output is partially correct
12 Partially correct 38 ms 51284 KB Output is partially correct
13 Partially correct 41 ms 49792 KB Output is partially correct
14 Partially correct 38 ms 49540 KB Output is partially correct
15 Partially correct 37 ms 49276 KB Output is partially correct
16 Partially correct 6 ms 42428 KB Output is partially correct
17 Partially correct 33 ms 49116 KB Output is partially correct
18 Partially correct 33 ms 49236 KB Output is partially correct
19 Partially correct 34 ms 49280 KB Output is partially correct
20 Partially correct 45 ms 51780 KB Output is partially correct
21 Partially correct 50 ms 53828 KB Output is partially correct
22 Partially correct 42 ms 51268 KB Output is partially correct