oj.uz

Submission #312678

# Submission time Handle Problem Language Result Execution time Memory
312678 2020-10-14T03:42:02 Z juggernaut Mechanical Doll (IOI18_doll) C++14
100 / 100
 163 ms 13100 KB 
#include"doll.h"
#include<bits/stdc++.h>
using namespace std;
void create_circuit(int M,vector<int>A){
    vector<vector<int>>after(M+1);
    vector<int>connected(M+1),x,y;
    A.push_back(0);
    int n=A.size(),i=0,s=0,id;
    for(;i<n;i++)
        after[A[i]].push_back(A[(i+1)%n]);
    int saizu=A.size();
    if(!saizu)id=0;
    else if(saizu==1)id=A[0];
    else{
        int j,k=1,K=0;
        while(k<saizu){
            k<<=1;
            K++;
        }
        vector<int>rev(k);
        for(j=0;j<k;j++)rev[j]=rev[j/2]/2|((j&1)<<(K-1));
        int iid=--s;
        for(int lvl=0;lvl<K-1;lvl++){
            for(j=0;j<(1<<lvl);j++){
                if((j<<(K-lvl))+(1<<(K-lvl))<=(k-saizu)){}
                else if((j<<(K-lvl))+(1<<(K-lvl-1))<=(k-saizu)){
                    x.push_back(iid);
                    y.push_back(--s);
                }
                else{
                    x.push_back(--s);
                    y.push_back(--s);
                }
            }
        }
        vector<int>go(k);
        int ptr=0;
        for(j=0;j<k;j++)
            if(rev[j]<(k-saizu)){}
            else go[rev[j]]=A[ptr++];
        for(j=0;j<k/2;j++){
            if((j<<1)+2<=(k-saizu)){}
            else if((j<<1)+1<=(k-saizu)){
                x.push_back(iid);
                y.push_back(go[(j<<1)+1]);
            }else{
                x.push_back(go[j<<1]);
                y.push_back(go[(j<<1)+1]);
            }
        }
        id=iid;
    }
    for(i=0;i<=M;i++)connected[i]=id;
    answer(connected,x,y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 8200 KB Output is correct
3 Correct 63 ms 6948 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 19 ms 3812 KB Output is correct
6 Correct 63 ms 10140 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 8200 KB Output is correct
3 Correct 63 ms 6948 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 19 ms 3812 KB Output is correct
6 Correct 63 ms 10140 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 77 ms 9572 KB Output is correct
9 Correct 97 ms 11168 KB Output is correct
10 Correct 163 ms 13100 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 8200 KB Output is correct
3 Correct 63 ms 6948 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 19 ms 3812 KB Output is correct
6 Correct 63 ms 10140 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 77 ms 9572 KB Output is correct
9 Correct 97 ms 11168 KB Output is correct
10 Correct 163 ms 13100 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 99 ms 10924 KB Output is correct
15 Correct 67 ms 7624 KB Output is correct
16 Correct 108 ms 9880 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 113 ms 11820 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 6712 KB Output is correct
3 Correct 57 ms 6184 KB Output is correct
4 Correct 73 ms 7608 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 6712 KB Output is correct
3 Correct 57 ms 6184 KB Output is correct
4 Correct 73 ms 7608 KB Output is correct
5 Correct 96 ms 10164 KB Output is correct
6 Correct 89 ms 9524 KB Output is correct
7 Correct 91 ms 9652 KB Output is correct
8 Correct 87 ms 9012 KB Output is correct
9 Correct 52 ms 6412 KB Output is correct
10 Correct 82 ms 8796 KB Output is correct
11 Correct 85 ms 9312 KB Output is correct
12 Correct 51 ms 6720 KB Output is correct
13 Correct 60 ms 7456 KB Output is correct
14 Correct 72 ms 7588 KB Output is correct
15 Correct 65 ms 7872 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 49 ms 6540 KB Output is correct
18 Correct 48 ms 6724 KB Output is correct
19 Correct 51 ms 6804 KB Output is correct
20 Correct 77 ms 8248 KB Output is correct
21 Correct 79 ms 8940 KB Output is correct
22 Correct 75 ms 7992 KB Output is correct