QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419156#2830. Data StructureYuJiaheRE 1ms5860kbC++232.9kb2024-05-23 18:17:482024-05-23 18:17:48

Judging History

你现在查看的是最新测评结果

  • [2024-05-23 18:17:48]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5860kb
  • [2024-05-23 18:17:48]
  • 提交

answer

#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int N = 200005;unordered_set<int> ept;
int n, m, o[N], a[N][2], ps[N][2], vi[N], ptr;
queue<pii> q1, q2, q3;vector<pii> ops;bool vv[N];
inline void clear(int i){o[i] = 0;}
inline void push(int i, int x){a[i][o[i] ++] = x, ps[x][ps[x][0] != 0] = i;}
inline int top(int i){return a[i][o[i] - 1];}
inline int pop(int i){ps[top(i)][ps[top(i)][0] != i] = 0;return a[i][-- o[i]];}
inline int size(int i){return o[i];}
inline void mov(int i, int j){ops.emplace_back(i, j), push(j, pop(i));}
inline void update(int v){if (vi[v] != 1) return;int x, y;
	if (top(x = ps[v][0]) == v && top(y = ps[v][1]) == v){
		if (size(x) + size(y) == 2) q1.emplace(x, y);
		if (size(x) + size(y) == 3) q2.emplace(x, y);
		if (size(x) + size(y) == 4) q3.emplace(x, y);vi[v] = 2;
	}
}
inline void ers(int x){vi[x] = 0;while (ptr <= n && !vi[ptr]) ptr ++;}
int main(){
	while (scanf("%d%d", &n, &m) != -1){
		ops.clear(), ept.clear(), ptr = 1;
		while (q1.size()) q1.pop();
		while (q2.size()) q2.pop();
		while (q3.size()) q3.pop();
		for (int i = 1;i <= n;i ++) ps[i][0] = ps[i][1] = 0, vi[i] = 1, vv[i] = 0;
		for (int i = 1, k;i <= m;i ++){
			scanf("%d", &k), clear(i);if (!k) ept.insert(i);
			for (int x;k --;) scanf("%d", &x), push(i, x);
			if (size(i) == 2 && a[i][0] == a[i][1]) ers(top(i));
		}
		for (int rt = 1, p;rt <= n;rt ++) if (!vv[rt]){p = 0;
			if (size(ps[rt][0]) == 1) p = ps[rt][0];
			if (size(ps[rt][1]) == 1) p = ps[rt][1];
			if (p) for (int u = rt, v, o;;p = o, u = v){
				vv[u] = 1, update(u);
				if (ps[u][0] != p) o = ps[u][0], v = a[o][a[o][0] == u];
				if (ps[u][1] != p) o = ps[u][1], v = a[o][a[o][0] == u];
				if (size(o) == 1) break;
			}
		}
		for (int rt = 1, p;rt <= n;rt ++) if (!vv[rt]){p = ps[rt][0];
			for (int u = rt, v, o;!vv[u];p = o, u = v){vv[u] = 1, update(u);
				if (ps[u][0] != p) o = ps[u][0], v = a[o][a[o][0] == u];
				if (ps[u][1] != p) o = ps[u][1], v = a[o][a[o][0] == u];
			}
		}
		while (ptr <= n){
			if (q1.size()){
				auto [x, y] = q1.front();q1.pop();
				ers(top(x)), mov(x, y), ept.insert(x);
			}
			else if (q2.size()){
				auto [x, y] = q2.front();q2.pop();
				if (size(x) > size(y)) swap(x, y);
				ers(top(x)), mov(y, x), update(top(y));
			}
			else if (q3.size()){if (ept.empty()) goto Nxt;
				auto [x, y] = q3.front();q3.pop();
				int z = *ept.begin();ept.erase(z), ers(top(x));
				mov(x, z), mov(y, z), update(top(x)), update(top(y));
			}
			else {if (ept.empty()) goto Nxt;
				int x = ps[ptr][0], y = *ept.begin();
				ept.erase(y), mov(x, y), update(top(x));
			}
		}printf("%d\n", ops.size());
		for (auto [x, y] : ops) printf("%d %d\n", x, y);
		continue;Nxt:printf("-1\n");
	}
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5860kb

input:

2 3
2 1 2
2 1 2
0
1 1
2 1 1
3 4
2 1 3
2 2 3
1 1
1 2

output:

3
1 3
2 3
1 2
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: -100
Runtime Error

input:

1 2
1 1
1 1
1 3
1 1
0
1 1
1 4
1 1
1 1
0
0
1 1
2 1 1
1 2
2 1 1
0
1 3
0
0
2 1 1

output:


result: