제출 #883796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883796		1e11	Parking (CEOI22_parking)	C++17	10 / 100	157 ms	24036 KiB

Main

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/priority_queue.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
/* ordered_set notes:
    .order_of_key(k): Number of items strictly smaller than k
    .find_by_order(k): k-th element in a set
*/
#define X first
#define Y second
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
#ifdef cychien
#define DE(...) do {\
	fprintf(stderr, "%s - %d : (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
    _DO(__VA_ARGS__);\
}while(0) 
template<typename I> void _DO(I&&x) {cerr << x << '\n';}
template<typename I, typename ...T> void _DO(I&&x,T&&...tail) {cerr << x << ", "; _DO(tail...);}
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#define IOS
#else
#define DE(...) 0
#define debug(...) 0  
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#endif
#define W(v) {for(auto it = (v).begin(); it != (v).end(); it++)cout << *it << " \n"[next(it) == (v).end()];}
#define pb emplace_back
#define mp make_pair
#define rsz resize
#define SZ(x) (ll)x.size()
#define AI(x) (x).begin(),(x).end()
#define SORT(x) sort(AI(x))
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
const int NF = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(){
    return uniform_int_distribution<int>(INT_MIN, INT_MAX)(rng);
}
/*
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using mint = modint998244353;
*/

const int MAXn = 200000;
const int TYPE_COUNT = 4;
enum State {
    ONE,
    UP,
    DOWN
};
int Mix(State a, State b){
    if (a > b) swap(a, b);
    if (a == ONE && b == ONE) return 0;
    if (a == ONE && b == UP) return 1;
    if (a == ONE && b == DOWN) return 2;
    if (a == UP && b == UP) return 3;
    if (a == UP && b == DOWN) return 3;
    if (a == DOWN && b == DOWN) return 3;
    assert(0);
}
int ptr[MAXn + 5];
vector<pii> stk[MAXn + 5];
pii pos[MAXn + 5][2];
State state[MAXn + 5][2];
vector<pii> ans;
set<int> type[TYPE_COUNT];
set<int> empty_stacks;
void refresh(int color){
    for (int i = 0; i < TYPE_COUNT; i++){
        if (type[i].find(color) != type[i].end()){
            type[i].erase(color);
            break;
        }
    }

    for (int i = 0; i < 2; i++){
        auto [which, where] = pos[color][i];
        int sz = SZ(stk[which]);

        if (sz == 0) return;
        else if (sz == 1) state[color][i] = ONE;
        else if (sz == 2 && where == 0) state[color][i] = DOWN;
        else if (sz == 2 && where == 1) state[color][i] = UP;
    }

    if (pos[color][0].X == pos[color][1].X) {
        return;
    }
    type[Mix(state[color][0], state[color][1])].insert(color);
}
void gao(int x, int y){
    if (SZ(stk[x]) < SZ(stk[y])) swap(x, y);
    for (int z : {x, y}){
        if (empty_stacks.find(z) != empty_stacks.end()){
            empty_stacks.erase(z);
        }
    }
    ans.pb(x, y);

    auto item = stk[x].back();
    auto [color, idx] = item;
    stk[x].pop_back();
    stk[y].pb(item);

    pos[color][idx] = pii(y, SZ(stk[y]) - 1);

    for (auto [c, _] : stk[x]) refresh(c);
    for (auto [c, _] : stk[y]) refresh(c);
    
    for (int z : {x, y}){
        if (stk[z].empty()){
            empty_stacks.insert(z);
        }
    }
}
bool the_end(){
    for (int i = 0; i < TYPE_COUNT; i++){
        if (!type[i].empty()){
            return false;
        }
    }
    return true;
}
void bye(){
    cout << "-1\n";
    exit(0);
}
int main() {
    IOS;
    int n, m; cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        if (x) stk[i].pb(x, ptr[x]);
        if (y) stk[i].pb(y, ptr[y]);

        if (x) pos[x][ptr[x]] = {i, 0};
        if (y) pos[y][ptr[y]] = {i, 1};

        if (x && y){
            state[x][ptr[x]] = DOWN;
            state[y][ptr[y]] = UP;
        }
        else if (x){
            state[x][ptr[x]] = ONE;
        }

        if (x) ptr[x]++;
        if (y) ptr[y]++;

        if (!x && !y) empty_stacks.insert(i);
    }

    for (int i = 1; i <= n; i++) refresh(i);

    while (!the_end()){
        if (!type[Mix(ONE, ONE)].empty()){
            int color = *type[Mix(ONE, ONE)].begin();

            auto [x, _] = pos[color][0];
            auto [y, __] = pos[color][1];

            gao(x, y);
            DE(183);
        }
        else if (!type[Mix(ONE, UP)].empty()){
            int color = *type[Mix(ONE, UP)].begin();

            auto [x, _] = pos[color][0];
            auto [y, __] = pos[color][1];

            gao(x, y);
            DE(192, color);
        }
        else {
            if (empty_stacks.empty()){
                bye();
            }

            int z = *empty_stacks.begin();

            if (!type[Mix(ONE, DOWN)].empty()){
                int color = *type[Mix(ONE, DOWN)].begin();

                auto [x, _] = pos[color][0];
                auto [y, __] = pos[color][1];

                if (SZ(stk[x]) == 2) swap(x, y);

                gao(y, z);
                gao(x, y);
                DE(210);
            }
            else {
                assert(!type[3].empty());
                int color = *type[3].begin();

                auto [arb_non_empty_stack, _] = pos[color][0];

                gao(arb_non_empty_stack, z);
                DE(220);
            }
        }
    }

    cout << SZ(ans) << '\n';
    for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
    return 0;
}

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

Main.cpp: In function 'int main()':
Main.cpp:30:17: warning: statement has no effect [-Wunused-value]
   30 | #define DE(...) 0
      |                 ^
Main.cpp:184:13: note: in expansion of macro 'DE'
  184 |             DE(183);
      |             ^~
Main.cpp:30:17: warning: statement has no effect [-Wunused-value]
   30 | #define DE(...) 0
      |                 ^
Main.cpp:193:13: note: in expansion of macro 'DE'
  193 |             DE(192, color);
      |             ^~
Main.cpp:30:17: warning: statement has no effect [-Wunused-value]
   30 | #define DE(...) 0
      |                 ^
Main.cpp:212:17: note: in expansion of macro 'DE'
  212 |                 DE(210);
      |                 ^~
Main.cpp:30:17: warning: statement has no effect [-Wunused-value]
   30 | #define DE(...) 0
      |                 ^
Main.cpp:221:17: note: in expansion of macro 'DE'
  221 |                 DE(220);
      |                 ^~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15