oj.uz

Submission #1096458

# Submission time Handle Problem Language Result Execution time Memory
1096458 2024-10-04T13:22:50 Z guagua0407 Mechanical Doll (IOI18_doll) C++17
100 / 100
 198 ms 26428 KB 
#include "doll.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int inf=1e9;

void create_circuit(int m, std::vector<int> a) {
    int n=a.size();
    int lg=__lg(n-1)+1;
    vector<int> state(1<<lg);
    vector<vector<int>> to(1<<lg,vector<int>(2,inf));
    for(int i=1;i<(1<<lg);i++){
        if(i*2<(1<<lg)) to[i][0]=-(i*2);
        if(i*2+1<(1<<lg)) to[i][1]=-(i*2+1);
    }
    vector<bool> ok(1<<lg);
    int bound=(1<<lg)-((n+1)/2);
    int diaob=0;
    for(int i=0;i<(1<<lg);i++){
        int nxt=((i==(1<<lg)-1)?0:(diaob<n-1?a[diaob+1]:-1));
        int cur=1;
        while(to[cur][state[cur]]!=inf){
            state[cur]^=1;
            cur=-to[cur][state[cur]^1];
        }
        if(nxt==0 or (nxt!=-1 and cur>=bound)){
            to[cur][state[cur]]=nxt;
            state[cur]^=1;
            ok[cur]=true;
            diaob++;
        }
        else{
            to[cur][state[cur]]=-1;
            state[cur]^=1;
        }
    }
    for(int i=(1<<lg)-1;i>=1;i--){
        if(i*2<(1<<lg)) ok[i]=ok[i]|ok[i*2];
        if(i*2+1<(1<<lg)) ok[i]=ok[i]|ok[i*2+1];
    }
    vector<int> vec;
    for(int i=1;i<(1<<lg);i++){
        if(ok[i]) vec.push_back(i);
    }
    vector<int> c(m+1,-1);
    c[0]=a[0];
    vector<int> x(vec.size()),y(vec.size());
    vector<int> id(1<<lg,inf);
    for(int i=0;i<(int)vec.size();i++){
        id[vec[i]]=i+1;
    }
    for(int i=1;i<(1<<lg);i++){
        if(i*2<(1<<lg) and !ok[-to[i][0]]) to[i][0]=-1;
        if(i*2+1<(1<<lg) and !ok[-to[i][1]]) to[i][1]=-1;
    }
    for(int i=0;i<(int)vec.size();i++){
        x[i]=to[vec[i]][0];
        y[i]=to[vec[i]][1];
        if(x[i]<0) x[i]=-id[-x[i]];
        if(y[i]<0) y[i]=-id[-y[i]];
        //if(x[i]==0) swap(x[i],y[i]);
    }
    answer(c,x,y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 40 ms 8032 KB Output is correct
3 Correct 66 ms 11604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 77 ms 13260 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 40 ms 8032 KB Output is correct
3 Correct 66 ms 11604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 77 ms 13260 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 88 ms 14844 KB Output is correct
9 Correct 171 ms 23492 KB Output is correct
10 Correct 192 ms 26428 KB Output is correct
11 Correct 0 ms 432 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 40 ms 8032 KB Output is correct
3 Correct 66 ms 11604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 77 ms 13260 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 88 ms 14844 KB Output is correct
9 Correct 171 ms 23492 KB Output is correct
10 Correct 192 ms 26428 KB Output is correct
11 Correct 0 ms 432 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 198 ms 26168 KB Output is correct
15 Correct 169 ms 22800 KB Output is correct
16 Correct 180 ms 25796 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 167 ms 26168 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 85 ms 13380 KB Output is correct
3 Correct 168 ms 21444 KB Output is correct
4 Correct 173 ms 23952 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 85 ms 13380 KB Output is correct
3 Correct 168 ms 21444 KB Output is correct
4 Correct 173 ms 23952 KB Output is correct
5 Correct 165 ms 24260 KB Output is correct
6 Correct 174 ms 24004 KB Output is correct
7 Correct 175 ms 24192 KB Output is correct
8 Correct 177 ms 23940 KB Output is correct
9 Correct 165 ms 21360 KB Output is correct
10 Correct 184 ms 24004 KB Output is correct
11 Correct 172 ms 24004 KB Output is correct
12 Correct 166 ms 21448 KB Output is correct
13 Correct 79 ms 13260 KB Output is correct
14 Correct 164 ms 21700 KB Output is correct
15 Correct 167 ms 21604 KB Output is correct
16 Correct 2 ms 1112 KB Output is correct
17 Correct 76 ms 13412 KB Output is correct
18 Correct 72 ms 13260 KB Output is correct
19 Correct 155 ms 21444 KB Output is correct
20 Correct 168 ms 24008 KB Output is correct
21 Correct 158 ms 24004 KB Output is correct
22 Correct 158 ms 24008 KB Output is correct