Submission #669457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669457	2022-12-06T13:46:39 Z	jiahng	Mechanical Doll (IOI18_doll)	C++14	6 / 100	99 ms	25880 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));
    assert(adj[x].size() >= build_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(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);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:2:
doll.cpp: In function 'int32_t solve(int32_t)':
doll.cpp:43:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   43 |     assert(adj[x].size() >= build_sz);
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	15556 KB	Output is correct
2	Correct	52 ms	19300 KB	Output is correct
3	Correct	36 ms	18976 KB	Output is correct
4	Correct	13 ms	15556 KB	Output is correct
5	Correct	21 ms	16708 KB	Output is correct
6	Correct	52 ms	20788 KB	Output is correct
7	Correct	16 ms	15576 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	15556 KB	Output is correct
2	Correct	52 ms	19300 KB	Output is correct
3	Correct	36 ms	18976 KB	Output is correct
4	Correct	13 ms	15556 KB	Output is correct
5	Correct	21 ms	16708 KB	Output is correct
6	Correct	52 ms	20788 KB	Output is correct
7	Correct	16 ms	15576 KB	Output is correct
8	Correct	54 ms	21492 KB	Output is correct
9	Correct	60 ms	21680 KB	Output is correct
10	Correct	86 ms	24964 KB	Output is correct
11	Correct	12 ms	15556 KB	Output is correct
12	Correct	12 ms	15580 KB	Output is correct
13	Correct	13 ms	15684 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	15556 KB	Output is correct
2	Correct	52 ms	19300 KB	Output is correct
3	Correct	36 ms	18976 KB	Output is correct
4	Correct	13 ms	15556 KB	Output is correct
5	Correct	21 ms	16708 KB	Output is correct
6	Correct	52 ms	20788 KB	Output is correct
7	Correct	16 ms	15576 KB	Output is correct
8	Correct	54 ms	21492 KB	Output is correct
9	Correct	60 ms	21680 KB	Output is correct
10	Correct	86 ms	24964 KB	Output is correct
11	Correct	12 ms	15556 KB	Output is correct
12	Correct	12 ms	15580 KB	Output is correct
13	Correct	13 ms	15684 KB	Output is correct
14	Incorrect	99 ms	25880 KB	wrong motion
15	Halted	0 ms	0 KB	-