Submission #669459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669459	2022-12-06T13:49:24 Z	jiahng	Mechanical Doll (IOI18_doll)	C++14	6 / 100	92 ms	27288 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define int 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];
vector <int32_t> X,Y;
 
vi build_idx[19], rev_build_idx[19];
int lg2[maxn];
int32_t solve(int32_t x){
    if (adj[x].size() == 1) return adj[x][0];
    
    int sz = adj[x].size();
    int build_sz = 1<<(63 - __builtin_clz(sz));
    if (build_sz < sz) build_sz <<= 1;     

    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 (!adj[x].empty()){
            if (idx & 1) Y[idx/2+offset] = adj[x].back();
            else X[idx/2+offset] = adj[x].back();
            adj[x].pop_back();
        }
    }
    return -(offset+1+1);
}
void create_circuit(int32_t M, std::vector<int32_t> A) {
  N = A.size();
  std::vector<int32_t> 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	13 ms	15556 KB	Output is correct
2	Correct	35 ms	19304 KB	Output is correct
3	Correct	36 ms	18904 KB	Output is correct
4	Correct	13 ms	15640 KB	Output is correct
5	Correct	25 ms	16708 KB	Output is correct
6	Correct	46 ms	20708 KB	Output is correct
7	Correct	13 ms	15540 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	15556 KB	Output is correct
2	Correct	35 ms	19304 KB	Output is correct
3	Correct	36 ms	18904 KB	Output is correct
4	Correct	13 ms	15640 KB	Output is correct
5	Correct	25 ms	16708 KB	Output is correct
6	Correct	46 ms	20708 KB	Output is correct
7	Correct	13 ms	15540 KB	Output is correct
8	Correct	55 ms	21532 KB	Output is correct
9	Correct	57 ms	21732 KB	Output is correct
10	Correct	78 ms	24932 KB	Output is correct
11	Correct	13 ms	15556 KB	Output is correct
12	Correct	13 ms	15556 KB	Output is correct
13	Correct	17 ms	15524 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	15556 KB	Output is correct
2	Correct	35 ms	19304 KB	Output is correct
3	Correct	36 ms	18904 KB	Output is correct
4	Correct	13 ms	15640 KB	Output is correct
5	Correct	25 ms	16708 KB	Output is correct
6	Correct	46 ms	20708 KB	Output is correct
7	Correct	13 ms	15540 KB	Output is correct
8	Correct	55 ms	21532 KB	Output is correct
9	Correct	57 ms	21732 KB	Output is correct
10	Correct	78 ms	24932 KB	Output is correct
11	Correct	13 ms	15556 KB	Output is correct
12	Correct	13 ms	15556 KB	Output is correct
13	Correct	17 ms	15524 KB	Output is correct
14	Incorrect	92 ms	27288 KB	wrong motion
15	Halted	0 ms	0 KB	-