Submission #659542

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
659542	2022-11-18T12:35:53 Z	jiahng	Mechanical Doll (IOI18_doll)	C++14	6 / 100	77 ms	32460 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 300010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N;
vi adj[maxn];
vi X,Y;

vi build_idx[19], rev_build_idx[19];
int lg2[maxn];
int solve(int x){
    if (adj[x].size() == 1) return adj[x][0];
    
    int sz = adj[x].size(), build_sz = sz & (-sz);
    
    int offset = (int)X.size() - 1;
    FOR(i,1,build_sz-1){
        X.pb(0); Y.pb(0);
    }
    FOR(i,2,build_sz-1){
        if (i&1) Y[i/2+offset] = i;
        else X[i/2+offset] = i;
    }
    FOR(i,0,build_sz-1){
        int idx = rev_build_idx[lg2[build_sz]][i] + build_sz;
        if (idx & 1) Y[idx/2+offset] = adj[x].back();
        else X[idx/2+offset] = adj[x].back();
        adj[x].pop_back();
    }
    adj[x].pb(-(offset+1+1));
    return solve(x);
}
void create_circuit(int M, std::vector<int> A) {
  N = A.size();
  std::vector<int> C(M + 1);
  FOR(i,0,N-2){
      adj[A[i]].pb(A[i+1]);
  }
  adj[A[N-1]].pb(0);

  FOR(i,1,M) reverse(all(adj[i]));
  int x = 1;
  FOR(i,0,18){
      lg2[x] = i; x <<= 1;
  }
  build_idx[1].pb(0); build_idx[1].pb(1);
  FOR(i,2,18){
      aFOR(j, build_idx[i-1]) build_idx[i].pb(j), build_idx[i].pb(j+(1<<(i-1)));
  }
  FOR(i,1,18){
      rev_build_idx[i] = vi(build_idx[i].size());
      FOR(j,0,build_idx[i].size()-1) rev_build_idx[i][build_idx[i][j]] = j;
  }
  

  C[0] = A[0];
  for (int i = 1; i <= M; ++i) if (!adj[i].empty()){
      C[i] = solve(i);
  }
  
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11464 KB	Output is correct
2	Correct	33 ms	15160 KB	Output is correct
3	Correct	28 ms	14848 KB	Output is correct
4	Correct	10 ms	11464 KB	Output is correct
5	Correct	19 ms	12616 KB	Output is correct
6	Correct	39 ms	16596 KB	Output is correct
7	Correct	10 ms	11464 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11464 KB	Output is correct
2	Correct	33 ms	15160 KB	Output is correct
3	Correct	28 ms	14848 KB	Output is correct
4	Correct	10 ms	11464 KB	Output is correct
5	Correct	19 ms	12616 KB	Output is correct
6	Correct	39 ms	16596 KB	Output is correct
7	Correct	10 ms	11464 KB	Output is correct
8	Correct	58 ms	17440 KB	Output is correct
9	Correct	75 ms	18552 KB	Output is correct
10	Correct	77 ms	22320 KB	Output is correct
11	Correct	10 ms	11464 KB	Output is correct
12	Correct	10 ms	11436 KB	Output is correct
13	Correct	11 ms	11464 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11464 KB	Output is correct
2	Correct	33 ms	15160 KB	Output is correct
3	Correct	28 ms	14848 KB	Output is correct
4	Correct	10 ms	11464 KB	Output is correct
5	Correct	19 ms	12616 KB	Output is correct
6	Correct	39 ms	16596 KB	Output is correct
7	Correct	10 ms	11464 KB	Output is correct
8	Correct	58 ms	17440 KB	Output is correct
9	Correct	75 ms	18552 KB	Output is correct
10	Correct	77 ms	22320 KB	Output is correct
11	Correct	10 ms	11464 KB	Output is correct
12	Correct	10 ms	11436 KB	Output is correct
13	Correct	11 ms	11464 KB	Output is correct
14	Runtime error	63 ms	32460 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-