#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, m;
int niz[maxn][2];
vector< pair<int, int> > pos[maxn];
vector< pair<int, int> > sol;
int nex[maxn], rev[maxn];
bool bio[2 * maxn];
set< int > emps;
vector< int > graph[2 * maxn];
vector< vector< int > > chains, cycles;
void stop() {
printf("-1\n");
exit(0);
}
bool istop(pair<int, int> t) {
int x = t.X;
int wh = t.Y;
if (wh == 1 || niz[x][1] == 0) return true;
return false;
}
void move(int x, int y) {
//printf("moving: %d %d\n", x + 1, y + 1);
int ind1 = 0, ind2 = -1;
if (niz[x][1] != 0) ind1 = 1;
if (niz[y][0] == 0) ind2 = 0;
else if (niz[y][1] == 0) ind2 = 1;
assert(ind2 >= 0 && niz[x][ind1] != 0);
sol.push_back({x + 1, y + 1});
if (ind2 == 0) emps.erase(y);
if (ind1 == 0) emps.insert(x);
swap(niz[x][ind1], niz[y][ind2]);
}
void calc_pos() {
emps.clear();
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
if (niz[i][j] != 0) pos[niz[i][j]].push_back({i, j});
}
if (niz[i][0] == 0 && niz[i][1] == 0) emps.insert(i);
}
}
vector< int > get_path(int x) {
vector< int > v;
int ptr = x;
int las = -1;
while (true) {
bio[ptr] = true;
v.push_back(ptr);
bool flag = false;
for (int tren : graph[ptr]) {
if (tren != las && !bio[tren]) {
las = ptr;
ptr = tren;
flag = true;
break;
}
}
if (!flag) break;
}
return v;
}
int price_chain(vector< int > &v) {
int cnt = 0;
for (int i = 0; i < v.size(); i += 2) {
if (!istop({v[i + 1] / 2, v[i + 1] % 2})) cnt++;
}
if (cnt <= 1) return 0;
cnt = 0;
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); i += 2) {
if (!istop({v[i + 1] / 2, v[i + 1] % 2})) cnt++;
}
reverse(v.begin(), v.end());
if (cnt <= 1) return 0;
return 1;
}
void solve_chain(vector< int > &v, int l, int r) {
//printf("chain solving\n");
if (l > r) return;
for (int i = l; i <= r; i += 2) {
if (v[i] % 2 == 1 && v[i + 1] % 2 == 1) {
if (emps.empty()) stop();
int ac = *emps.begin();
move(v[i] / 2, ac);
move(v[i + 1] / 2, ac);
solve_chain(v, l, i - 1);
solve_chain(v, i + 2, r);
return;
}
}
for (int i = l; i <= r; i += 2) {
if (v[i] % 2 == 0 && v[i + 1] % 2 == 0) {
for (int j = l; j < i; j += 2)
move(v[j + 1] / 2, v[j] / 2);
for (int j = r; j > i + 1; j -= 2)
move(v[j - 1] / 2, v[j] / 2);
move(v[i] / 2, v[i + 1] / 2);
return;
}
}
if (v[l + 1] % 2 == 1) {
for (int i = l; i <= r; i += 2)
move(v[i + 1] / 2, v[i] / 2);
} else {
for (int i = r; i >= l; i -= 2)
move(v[i - 1] / 2, v[i] / 2);
}
}
inline int get(int x) {
return niz[x / 2][x % 2];
}
int price_cycle(vector< int > &v) {
for (int i = 0; i < v.size(); i++) {
if (get(v[i]) == get(v[(i + 1) % v.size()]) && v[i] % 2 == 1 && v[i + 1] % 2 == 1) {
vector< int > ne;
for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
return price_chain(ne) + 1;
}
}
return 1;
}
void solve_cycle(vector< int > &v) {
//printf("cycle solving\n");
for (int i = 0; i < v.size(); i++) {
if (get(v[i]) == get(v[(i + 1) % v.size()]) && v[i] % 2 == 1 && v[i + 1] % 2 == 1) {
vector< int > ne;
for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
if (emps.empty()) stop();
int x = *emps.begin();
move(v[i] / 2, x);
move(v[(i + 1) % v.size()] / 2, x);
solve_chain(ne, 0, ne.size() - 1);
return;
}
}
if (emps.empty()) stop();
int x = *emps.begin();
int ind = -1;
for (int i = 0; i < v.size(); i++) {
if (v[i] % 2 == 1) ind = i;
}
move(v[ind] / 2, x);
for (int i = 0; i < v.size() - 1; i += 2) {
move(v[(ind + 2 + i) % v.size()] / 2, v[(ind + 1 + i) % v.size()] / 2);
}
move(v[(ind + v.size() - 1) % v.size()] / 2, x);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
for (int j = 0; j < 2; j++)
scanf("%d", &niz[i][j]);
calc_pos();
for (int i = 1; i <= n; i++) {
bool flag = true;
for (int j = 0; j < 2; j++) {
int x = pos[i][j].X;
int y = pos[i][j].Y;
if (y != 0 || niz[x][1] != 0) flag = false;
}
if (flag) move(pos[i][0].X, pos[i][1].Y);
pos[i].clear();
}
calc_pos();
for (int i = 1; i <= n; i++) {
int ax = pos[i][0].X;
int ay = pos[i][0].Y;
int bx = pos[i][1].X;
int by = pos[i][1].Y;
graph[2 * ax + ay].push_back(2 * bx + by);
graph[2 * bx + by].push_back(2 * ax + ay);
}
for (int i = 0; i < m; i++) {
if (niz[i][0] > 0 && niz[i][1] > 0 && niz[i][0] != niz[i][1]) {
graph[i * 2].push_back(2 * i + 1);
graph[i * 2 + 1].push_back(2 * i);
}
}
for (int i = 0; i < 2 * m; i++) {
if (graph[i].size() == 1 && !bio[i]) {
vector< int > v = get_path(i);
if (v.size() == 2) {
if (v[0] / 2 == v[1] / 2) continue;
move(v[0] / 2, v[1] / 2);
continue;
}
chains.push_back(v);
}
}
for (int i = 0; i < 2 * m; i++) {
if (!bio[i] && graph[i].size() == 2) {
vector< int > v = get_path(i);
cycles.push_back(v);
}
}
vector< vector< int > > tr;
for (auto &iter : chains) {
if (price_chain(iter) == 0) solve_chain(iter, 0, iter.size() - 1);
else tr.push_back(iter);
}
for (auto &iter : tr) solve_chain(iter, 0, iter.size() - 1);
tr.clear();
for (auto &iter : cycles) {
if (price_cycle(iter) == 1) solve_cycle(iter);
else tr.push_back(iter);
}
for (auto &iter : tr) solve_cycle(iter);
printf("%d\n", sol.size());
for (auto iter : sol) printf("%d %d\n", iter.X, iter.Y);
return 0;
}
Compilation message
Main.cpp: In function 'int price_chain(std::vector<int>&)':
Main.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < v.size(); i += 2) {
| ~~^~~~~~~~~~
Main.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < v.size(); i += 2) {
| ~~^~~~~~~~~~
Main.cpp: In function 'int price_cycle(std::vector<int>&)':
Main.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void solve_cycle(std::vector<int>&)':
Main.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for (int j = 0; j < v.size() - 2; j++) ne.push_back(v[(i + j + 2) % v.size()]);
| ~~^~~~~~~~~~~~~~
Main.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp:176:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for (int i = 0; i < v.size() - 1; i += 2) {
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:250:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
250 | printf("%d\n", sol.size());
| ~^ ~~~~~~~~~~
| | |
| int std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
| %ld
Main.cpp:183:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | scanf("%d", &niz[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
43768 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
29052 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
