QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419156 | #2830. Data Structure | YuJiahe | RE | 1ms | 5860kb | C++23 | 2.9kb | 2024-05-23 18:17:48 | 2024-05-23 18:17:48 |
Judging History
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