oj.uz

Submission #1014331

# Submission time Handle Problem Language Result Execution time Memory
1014331 2024-07-04T16:49:02 Z Dzadzo Mechanical Doll (IOI18_doll) C++14
44.4019 / 100
 165 ms 33920 KB 
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 500000
using namespace std;
vi f(MAXN+1);
vector < pair < int , pii > > go(int val) {
    if (val==2) {
        f[1]=-1;
        return { { -1 ,{ 1 ,2 } } };
    }
    vector <pair <int,pii>>arr=go(val/2);
    vi newf(MAXN+1);
    for (int i=1;i<=val/4;i++) {
        newf[i]=f[i]*2;
        newf[i+val/4]=f[i]*2-1;
    }
    f=newf;
    vector < pair <int,pii> > res ={ {-1 , { -2 , -3 } } };
 
    for (auto x:arr) {
        int sw=x.F;
        int X=x.S.F;
        int Y=x.S.S;
        if (X<0 && Y<0) {
            res.pb({sw*2,{X*2,Y*2}});
            res.pb({sw*2-1,{X*2-1,Y*2-1}});
        }else{
            res.pb({sw*2,{X*2-1,Y*2-1}});
            res.pb({sw*2-1,{X*2,Y*2}});
        }
    }
    return res;
}
 
void dfs(int v,int p,int dir,vi &X,vi &Y) {
 
    if (X[-v-1] == -1 && Y[-v-1] == -1) {
        if (dir==0)X[-p-1]=-1;else Y[-p-1] = -1 ;
    }
    if (X[-v-1] != -1 && X[-v-1] < 0) dfs(X[-v-1],v,0,X,Y);
    if (Y[-v-1] != -1 && Y[-v-1] < 0) dfs(Y[-v-1],v,1,X,Y);
 
}
vi g(MAXN+1,-1);
vi z(MAXN+1);
int CNT=0;
void label(int v,vi &X,vi &Y) {
 
    g[-v-1]=--CNT;
    // cout<<CNT<<'\n';
    if (X[-v-1] != -1 && X[-v-1] < 0) label(X[-v-1],X,Y);
    if (Y[-v-1] != -1 && Y[-v-1] < 0) label(Y[-v-1],X,Y);
 
}
vector <pair <int , pii >> ans;
void solve(int v,vi &X,vi &Y) {
    int k1,k2;
    if (X[-v-1]<0)k1=g[-X[-v-1]-1];else k1=z[X[-v-1]];
    if (Y[-v-1]<0)k2=g[-Y[-v-1]-1];else k2=z[Y[-v-1]];
 
    ans.pb({g[-v-1],{k1,k2}});
    if (X[-v-1] != -1 && X[-v-1] < 0) solve(X[-v-1],X,Y);
    if (Y[-v-1] != -1 && Y[-v-1] < 0) solve(Y[-v-1],X,Y);
}
void create_circuit(int m, vi a) {
    a.pb(0);
    int n=a.size();
    int k=1;
    while (k<2*n)k*=2;
    k/=2;
 
    vi C(m+1);
    for (int i=0;i<=m;i++)C[i]=-1;
 
    vector <pair <int,pii>>arr=go(k);
    vi X(arr.size()),Y(arr.size());
 
 
    for (auto t:arr) {
        X[-t.F-1]=t.S.F;
        Y[-t.F-1]=t.S.S;
    }
 
 
    set <int> s;
    for (int i=1;i<=k;i++)s.insert(i);
 
 
    int cnt=k-n;
    int ind=1;
    while (cnt>0) {
        if (cnt==1) {
            s.erase(X[-f[ind]-1]);
            X[-f[ind]-1]=-1;
            break;
        }
        s.erase(X[-f[ind]-1]);
        s.erase(Y[-f[ind]-1]);
        X[-f[ind]-1]=-1;
        Y[-f[ind]-1]=-1;
        cnt-=2;
        ind++;
    }
    dfs(-1,0,0,X,Y);
 
    label(-1,X,Y);
 
    int cur=-1;
    for (int x:s)z[x]=a[++cur];
 
    solve(-1,X,Y);
    /*cout<<arr.size()<<"\n";
    for (int i=0;i<arr.size();i++)cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<'\n';
    cout<<"---\n";*/
    // cout<<CNT<<'\n';
    vi ansX(-CNT),ansY(-CNT);
    for (auto x:ans) {
        ansX[-x.F-1] = x.S.F;
        ansY[-x.F-1] = x.S.S;
    }
      answer(C,ansX,ansY);
 
    // for (int i=0;i<ansX.size();i++) {
    //     cout<< -i-1 << " " << ansX[i] <<" "<< ansY[i]<<'\n';
    // }
}
 
// signed main() {
//     int m;
//     cin>>m;
//     int n;
//     cin>>n;
//     vi a(n);
//     for (int i=1;i<=n;i++)cin>>a[i-1];
//     create_circuit(m,a);
// }

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8120 KB Output is correct
2 Incorrect 72 ms 21348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8120 KB Output is correct
2 Incorrect 72 ms 21348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8120 KB Output is correct
2 Incorrect 72 ms 21348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
10.80046701 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 8120 KB Output is partially correct
2 Partially correct 142 ms 31640 KB Output is partially correct
3 Partially correct 141 ms 31516 KB Output is partially correct
4 Partially correct 130 ms 33292 KB Output is partially correct

Subtask #6
33.60145292 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 8120 KB Output is partially correct
2 Partially correct 142 ms 31640 KB Output is partially correct
3 Partially correct 141 ms 31516 KB Output is partially correct
4 Partially correct 130 ms 33292 KB Output is partially correct
5 Partially correct 142 ms 33920 KB Output is partially correct
6 Partially correct 130 ms 33548 KB Output is partially correct
7 Partially correct 139 ms 33744 KB Output is partially correct
8 Partially correct 131 ms 33556 KB Output is partially correct
9 Partially correct 147 ms 31520 KB Output is partially correct
10 Partially correct 122 ms 33552 KB Output is partially correct
11 Partially correct 120 ms 33300 KB Output is partially correct
12 Partially correct 142 ms 31520 KB Output is partially correct
13 Partially correct 165 ms 31772 KB Output is partially correct
14 Partially correct 132 ms 31744 KB Output is partially correct
15 Partially correct 153 ms 32028 KB Output is partially correct
16 Partially correct 7 ms 8632 KB Output is partially correct
17 Correct 48 ms 21960 KB Output is correct
18 Partially correct 125 ms 31512 KB Output is partially correct
19 Partially correct 124 ms 31696 KB Output is partially correct
20 Partially correct 112 ms 33496 KB Output is partially correct
21 Partially correct 113 ms 33292 KB Output is partially correct
22 Partially correct 110 ms 33264 KB Output is partially correct