oj.uz

Submission #525093

# Submission time Handle Problem Language Result Execution time Memory
525093 2022-02-10T16:52:21 Z leaked Mechanical Doll (IOI18_doll) C++14
53 / 100
 149 ms 16656 KB 
#include <bits/stdc++.h>
#include "doll.h"


#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

void create_circuit(int m,vec<int> a){
    vec<int>c(m+1);
    vec<int> cnt(m+1,0);
    vec<vec<int>> goes(m+1,vec<int>());
    int n=0;
    for(int i=0;i<sz(a);i++){
        int nxt=(i+1==sz(a)?0:a[i+1]);
        goes[a[i]].pb(nxt);
    }
    vec<int>x,y;
    vec<int>curt;
    for(int i=1;i<=m;i++){
        if(sz(goes[i])==1){
            c[i]=goes[i].back();
            continue;
        }
        if(!sz(goes[i])) continue;
        vec<int>cur(sz(goes[i]),0);
        int lvl=ceil((double)log2(sz(goes[i])));
        int lt=lvl;
        while(sz(cur)!=pw(lvl)) cur.pb(0);
        while(lvl!=0){
            vec<int>nc;
            for(int j=0;j<sz(cur);j+=2){
                nc.pb(-(++n));
//                cout<<"EDGE "<<nc.back()<<' '<<cur[j]<<' '<<cur[j+1]<<endl;
                x.pb(cur[j]);y.pb(cur[j+1]);
                curt.pb(0);
            }
            cur=nc;
            --lvl;
        }
        reverse(all(goes[i]));
        lvl=lt;
//        if(i==4){
//            i=4;
//        }
        while(sz(goes[i])!=pw(lvl)) goes[i].pb(cur.back());
        while(sz(goes[i])){
            int v=cur.back();
            while(1){
                v=-v;
//                cout<<"V "<<v<<' '<<sz(x)<<endl;
                int &u=(curt[v-1]?y[v-1]:x[v-1]);
                curt[v-1]^=1;
                if(u>=0){
                    u=goes[i].back(),goes[i].pop_back();
                    break;
                }
                v=u;
            }
        }
        c[i]=cur.back();
    }
    c[0]=a[0];
//        cout<<sz(c)<<' '<<sz(x)<<' '<<sz(y)<<endl;
//    for(auto &z : c)
//        cout<<z<<' ';
//    cout<<endl;
//    for(int i=0;i<sz(x);i++){
//        if(x[i]==y[i]){
//
//        }
//    }
//        cout<<x[i]<<' '<<y[i]<<endl;

    answer(c, 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 29 ms 6732 KB Output is correct
3 Correct 26 ms 5444 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 4172 KB Output is correct
6 Correct 33 ms 8004 KB Output is correct
7 Correct 0 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 29 ms 6732 KB Output is correct
3 Correct 26 ms 5444 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 4172 KB Output is correct
6 Correct 33 ms 8004 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 56 ms 7996 KB Output is correct
9 Correct 53 ms 9240 KB Output is correct
10 Correct 112 ms 11832 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 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 29 ms 6732 KB Output is correct
3 Correct 26 ms 5444 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 4172 KB Output is correct
6 Correct 33 ms 8004 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 56 ms 7996 KB Output is correct
9 Correct 53 ms 9240 KB Output is correct
10 Correct 112 ms 11832 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 93 ms 12060 KB Output is correct
15 Correct 54 ms 7244 KB Output is correct
16 Correct 78 ms 10920 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 84 ms 13048 KB Output is correct
21 Correct 0 ms 288 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 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 0 ms 204 KB Output is partially correct
2 Correct 64 ms 6836 KB Output is correct
3 Partially correct 128 ms 11488 KB Output is partially correct
4 Partially correct 128 ms 12688 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 204 KB Output is partially correct
2 Correct 64 ms 6836 KB Output is correct
3 Partially correct 128 ms 11488 KB Output is partially correct
4 Partially correct 128 ms 12688 KB Output is partially correct
5 Partially correct 105 ms 14712 KB Output is partially correct
6 Partially correct 116 ms 15340 KB Output is partially correct
7 Partially correct 113 ms 15128 KB Output is partially correct
8 Partially correct 113 ms 15620 KB Output is partially correct
9 Partially correct 111 ms 10612 KB Output is partially correct
10 Partially correct 149 ms 16656 KB Output is partially correct
11 Partially correct 115 ms 16156 KB Output is partially correct
12 Partially correct 75 ms 10872 KB Output is partially correct
13 Partially correct 74 ms 10276 KB Output is partially correct
14 Partially correct 72 ms 10116 KB Output is partially correct
15 Partially correct 68 ms 9892 KB Output is partially correct
16 Partially correct 3 ms 588 KB Output is partially correct
17 Partially correct 59 ms 8968 KB Output is partially correct
18 Partially correct 62 ms 8772 KB Output is partially correct
19 Partially correct 65 ms 9380 KB Output is partially correct
20 Partially correct 84 ms 12272 KB Output is partially correct
21 Partially correct 109 ms 14388 KB Output is partially correct
22 Partially correct 78 ms 11512 KB Output is partially correct