QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385569 | #2830. Data Structure | ucup-team1209 | RE | 0ms | 13148kb | C++14 | 3.3kb | 2024-04-10 21:19:38 | 2024-04-10 21:19:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
#ifdef zqj
freopen("a.in","r",stdin);
#endif
}
typedef long long ll;
#define sz 202020
int n,m;
vector<int>st[sz];
vector<int>pos[sz];
set<int>num[3];
vector<pii>ans;
void output() {
cout<<ans.size()<<'\n';
for (auto [x,y]:ans) cout<<x<<' '<<y<<'\n';
}
void mov(int f,int t) {
assert(f!=t);
assert(st[f].size());
assert(st[t].size()==0u||(st[t].size()==1u&&st[t][0]==st[f].back()));
for (auto p:{f,t}) num[st[p].size()].erase(p);
ans.push_back({f,t});
int x=st[f].back();
st[t].push_back(x),st[f].pop_back();
rep(i,0,1) if (pos[x][i]==f) {pos[x][i]=t; break;}
num[st[f].size()].insert(f);
if (st[t].size()!=1u) num[st[t].size()].insert(t);
}
int ok(int x){return pos[x][0]==pos[x][1];}
void check(int x) {
assert(!ok(x));
int p0=pos[x][0],p1=pos[x][1];
if (st[p1].size()==1u) swap(p0,p1);
if (st[p0].size()==1u) {
if (st[p1].size()==1u||st[p1][1]==x) {
mov(p1,p0);
if (st[p1].size()) check(st[p1][0]);
return;
}
if (num[0].size()) {
int pp=*(num[0].begin()),t=p1;
while (233) {
int y=st[t][1];
t^=pos[y][0]^pos[y][1];
if (st[t][1]==y) {
int yy=st[t][0];
mov(t,pp);
check(y);
check(yy);
return;
}
}
}
}
}
void work() {
#define NO return cout<<"-1\n",void()
rep(i,1,m) st[i].clear();
rep(i,1,n) pos[i].clear();
rep(i,0,2) num[i].clear();
ans.clear();
rep(i,1,m) {
int k,x; cin>>k;
rep(_,1,k) cin>>x,st[i].push_back(x),pos[x].push_back(i);
if (k!=2||(k==2&&st[i][0]!=st[i][1])) num[k].insert(i);
}
if (n==m) {
if (num[2].size()) NO;
output();
return;
}
rep(i,1,n) if (!ok(i)) check(i);
if (num[1].size()||num[2].size()) {
if (!num[0].size()) NO;
while (num[1].size()) {
int p=*(num[1].begin());
check(st[p][0]);
}
assert(num[0].size());
rep(i,1,n) if (!ok(i)&&st[pos[i][0]][1]==i&&st[pos[i][1]][1]==i) {
int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
mov(p0,pp),mov(p1,pp);
check(st[p0].back());
if (st[p1].size()&&!ok(st[p1][0])) check(st[p1].back());
if (!num[0].size()) {
assert(m==n+1);
NO;
}
}
rep(i,1,n) if (!ok(i)) {
int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
if (st[p0][1]!=i) swap(p0,p1);
mov(p0,pp);
check(st[p0].back());
assert(num[0].size());
}
rep(i,1,n) assert(ok(i));
}
output();
}
int main() {
file();
ios::sync_with_stdio(false),cin.tie(0);
while (cin>>n>>m) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 13148kb
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: 0
Accepted
time: 0ms
memory: 13084kb
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:
1 1 2 1 1 3 1 1 2 0 0 0
result:
ok 6 cases passed. max #moves/#balls = 1.000000000
Test #3:
score: -100
Runtime Error
input:
2 4 1 1 1 2 1 2 1 1 2 5 1 1 1 2 0 1 1 1 2 2 6 0 1 1 0 1 1 1 2 1 2 2 4 1 2 1 1 1 1 1 2 2 5 1 1 0 1 2 1 2 1 1 2 6 1 2 0 1 1 0 1 1 1 2 2 4 1 1 1 2 1 2 1 1 2 5 0 1 2 1 1 1 1 1 2 2 6 1 1 0 1 2 1 2 0 1 1 2 3 2 2 1 1 1 1 2 2 4 2 2 1 1 1 0 1 2 2 5 1 1 0 1 2 2 1 2 0 2 3 1 2 2 1 2 1 1 2 4 1 1 2 2 1 1 2 0 2 5 ...