답안 #669457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
669457	2022-12-06T13:46:39 Z	jiahng	자동 인형 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-