Submission #669450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
669450	2022-12-06T13:40:29 Z	jiahng	Mechanical Doll (IOI18_doll)	C++14	6 / 100	74 ms	31040 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();
    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(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:42:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     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	33 ms	15184 KB	Output is correct
3	Correct	27 ms	14868 KB	Output is correct
4	Correct	10 ms	11456 KB	Output is correct
5	Correct	18 ms	12616 KB	Output is correct
6	Correct	39 ms	16584 KB	Output is correct
7	Correct	9 ms	11464 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	33 ms	15184 KB	Output is correct
3	Correct	27 ms	14868 KB	Output is correct
4	Correct	10 ms	11456 KB	Output is correct
5	Correct	18 ms	12616 KB	Output is correct
6	Correct	39 ms	16584 KB	Output is correct
7	Correct	9 ms	11464 KB	Output is correct
8	Correct	53 ms	17316 KB	Output is correct
9	Correct	59 ms	17640 KB	Output is correct
10	Correct	74 ms	20864 KB	Output is correct
11	Correct	10 ms	11512 KB	Output is correct
12	Correct	10 ms	11464 KB	Output is correct
13	Correct	9 ms	11464 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	33 ms	15184 KB	Output is correct
3	Correct	27 ms	14868 KB	Output is correct
4	Correct	10 ms	11456 KB	Output is correct
5	Correct	18 ms	12616 KB	Output is correct
6	Correct	39 ms	16584 KB	Output is correct
7	Correct	9 ms	11464 KB	Output is correct
8	Correct	53 ms	17316 KB	Output is correct
9	Correct	59 ms	17640 KB	Output is correct
10	Correct	74 ms	20864 KB	Output is correct
11	Correct	10 ms	11512 KB	Output is correct
12	Correct	10 ms	11464 KB	Output is correct
13	Correct	9 ms	11464 KB	Output is correct
14	Runtime error	50 ms	31040 KB	Execution killed with signal 6
15	Halted	0 ms	0 KB	-