#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;
}
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);
| ^~
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);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7632 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 |
7516 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 |
7512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 10 |
Correct |
3 ms |
7512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
157 ms |
24036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
7768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
7772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7632 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 |
7516 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 |
7512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 10 |
Correct |
3 ms |
7512 KB |
Output is correct |
| 11 |
Incorrect |
157 ms |
24036 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
