제출 #558398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558398		maomao90	자동 인형 (IOI18_doll)	C++17	10 / 100	1 ms	468 KiB

doll

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;
#include "doll.h"

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int n, m;
vi a;
int x[MAXN * 2], y[MAXN * 2];
int tog[MAXN * 2];
int lg;

int ptr = 1;
int dnc(int lo, int hi, int k, int n) {
    if (lo == hi) return 0;
    int u = ptr++;
    int mid = lo + hi >> 1;
    if (n >> k & 1 ^ 1) {
        x[u] = -1;
        y[u] = -dnc(mid + 1, hi, k - 1, n);
    } else {
        x[u] = -dnc(lo, mid, k - 1, n);
        y[u] = -dnc(mid + 1, hi, k - 1, (1 << lg) - 1);
    }
    cerr << u << ": " << x[u] << ' ' << y[u] << '\n';
    return u;
}
void sim(int u, int t) {
    //cerr << u << " " << tog[u] << '\n';
    tog[u] ^= 1;
    if (tog[u] == 1) {
        if (x[u] == 0) {
            x[u] = t;
        } else {
            sim(-x[u], t);
        }
    } else {
        if (y[u] == 0) {
            y[u] = t;
        } else {
            sim(-y[u], t);
        }
    }
}

void create_circuit(int M, vi A) {
    a = A;
    n = A.size();
    m = M;
    a.pb(0);
    vi c(m + 1);
    c[0] = a[0];
    REP (i, 1, m + 1) {
        c[i] = -1;
    }
    lg = 0;
    while ((1 << lg) < n) {
        lg++;
    }
    dnc(0, (1 << lg) - 1, lg - 1, n - 1);
    REP (i, 0, n) {
        sim(1, a[i + 1]);
    }
    vi rx, ry;
    REP (i, 1, ptr) {
        rx.pb(x[i]);
        ry.pb(y[i]);
    }
    REP (i, 0, m + 1) {
        cerr << c[i] << ' ';
    }
    cerr << '\n';
    REP (i, 1, ptr) {
        cerr << -i << ": " << x[i] << ' ' << y[i] << '\n';
    }
    assert(ptr <= n + 1);
    answer(c, rx, ry);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'int dnc(int, int, int, int)':
doll.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
doll.cpp:49:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   49 |     if (n >> k & 1 ^ 1) {
      |         ~~~~~~~^~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56