Submission #669453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669453	2022-12-06T13:43:31 Z	jiahng	Mechanical Doll (IOI18_doll)	C++14	6 / 100	76 ms	42492 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 = sz & (-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	13 ms	15556 KB	Output is correct
2	Correct	35 ms	19308 KB	Output is correct
3	Correct	34 ms	18936 KB	Output is correct
4	Correct	12 ms	15556 KB	Output is correct
5	Correct	20 ms	16708 KB	Output is correct
6	Correct	44 ms	20716 KB	Output is correct
7	Correct	14 ms	15620 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	19308 KB	Output is correct
3	Correct	34 ms	18936 KB	Output is correct
4	Correct	12 ms	15556 KB	Output is correct
5	Correct	20 ms	16708 KB	Output is correct
6	Correct	44 ms	20716 KB	Output is correct
7	Correct	14 ms	15620 KB	Output is correct
8	Correct	53 ms	21532 KB	Output is correct
9	Correct	57 ms	21696 KB	Output is correct
10	Correct	76 ms	24952 KB	Output is correct
11	Correct	12 ms	15556 KB	Output is correct
12	Correct	13 ms	15556 KB	Output is correct
13	Correct	13 ms	15620 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	19308 KB	Output is correct
3	Correct	34 ms	18936 KB	Output is correct
4	Correct	12 ms	15556 KB	Output is correct
5	Correct	20 ms	16708 KB	Output is correct
6	Correct	44 ms	20716 KB	Output is correct
7	Correct	14 ms	15620 KB	Output is correct
8	Correct	53 ms	21532 KB	Output is correct
9	Correct	57 ms	21696 KB	Output is correct
10	Correct	76 ms	24952 KB	Output is correct
11	Correct	12 ms	15556 KB	Output is correct
12	Correct	13 ms	15556 KB	Output is correct
13	Correct	13 ms	15620 KB	Output is correct
14	Runtime error	69 ms	42492 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-