Submission #669449

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669449	2022-12-06T13:39:56 Z	jiahng	Mechanical Doll (IOI18_doll)	C++14	6 / 100	78 ms	32548 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);
    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(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);
}

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 'int solve(int)':
doll.cpp:41:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     assert(adj[x].size() <= build_sz);
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11464 KB	Output is correct
2	Correct	35 ms	15688 KB	Output is correct
3	Correct	30 ms	15284 KB	Output is correct
4	Correct	11 ms	11516 KB	Output is correct
5	Correct	19 ms	12616 KB	Output is correct
6	Correct	43 ms	17192 KB	Output is correct
7	Correct	10 ms	11436 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11464 KB	Output is correct
2	Correct	35 ms	15688 KB	Output is correct
3	Correct	30 ms	15284 KB	Output is correct
4	Correct	11 ms	11516 KB	Output is correct
5	Correct	19 ms	12616 KB	Output is correct
6	Correct	43 ms	17192 KB	Output is correct
7	Correct	10 ms	11436 KB	Output is correct
8	Correct	62 ms	18252 KB	Output is correct
9	Correct	53 ms	18572 KB	Output is correct
10	Correct	78 ms	22412 KB	Output is correct
11	Correct	11 ms	11440 KB	Output is correct
12	Correct	12 ms	11436 KB	Output is correct
13	Correct	12 ms	11436 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11464 KB	Output is correct
2	Correct	35 ms	15688 KB	Output is correct
3	Correct	30 ms	15284 KB	Output is correct
4	Correct	11 ms	11516 KB	Output is correct
5	Correct	19 ms	12616 KB	Output is correct
6	Correct	43 ms	17192 KB	Output is correct
7	Correct	10 ms	11436 KB	Output is correct
8	Correct	62 ms	18252 KB	Output is correct
9	Correct	53 ms	18572 KB	Output is correct
10	Correct	78 ms	22412 KB	Output is correct
11	Correct	11 ms	11440 KB	Output is correct
12	Correct	12 ms	11436 KB	Output is correct
13	Correct	12 ms	11436 KB	Output is correct
14	Runtime error	58 ms	32548 KB	Execution killed with signal 6
15	Halted	0 ms	0 KB	-