oj.uz

답안 #883800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883800 2023-12-06T05:16:30 Z 1e11 Parking (CEOI22_parking) C++17
20 / 100
 245 ms 25548 KB 
#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 = 6;
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 4;
    if (a == DOWN && b == DOWN) return 5;
    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(UP, UP)].empty()){
                int color = *type[Mix(UP, UP)].begin();

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

                assert(_ == 1);

                gao(x, z);
            }
            else if (!type[Mix(UP, DOWN)].empty()){
                int color = *type[Mix(UP, DOWN)].begin();

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

                gao(x, z);
            }
            else 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);
            }
        }
    }

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

Compilation message

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);
      |             ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7768 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 22724 KB Output is correct
2 Correct 245 ms 25296 KB Output is correct
3 Correct 139 ms 22916 KB Output is correct
4 Correct 114 ms 22480 KB Output is correct
5 Correct 221 ms 25548 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 3 ms 7512 KB Output is correct
7 Correct 2 ms 7512 KB Output is correct
8 Incorrect 2 ms 7516 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7768 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 174 ms 22724 KB Output is correct
12 Correct 245 ms 25296 KB Output is correct
13 Correct 139 ms 22916 KB Output is correct
14 Correct 114 ms 22480 KB Output is correct
15 Correct 221 ms 25548 KB Output is correct
16 Incorrect 2 ms 7516 KB Output isn't correct
17 Halted 0 ms 0 KB -