QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #82012 | #2830. Data Structure | AHSFNU_team_0 | WA | 59ms | 14448kb | C++14 | 4.1kb | 2023-02-26 21:33:08 | 2023-02-26 21:33:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,vis[400005],pos[400005],ans;
int ax[500005],ay[500005],cnt;
vector<int> stk[200005];
set<int> s[2][2],t[3],ept;
inline int opp(int u){
if(u>n)return u-n;
return u+n;
}
inline void ins(int u,int v){
if(u!=stk[pos[u]].back())return;
if(v!=stk[pos[v]].back())return;
if(pos[u]==pos[v])return;
if(u>v)swap(u,v);
if(stk[pos[u]].size()<2 || stk[pos[v]].size()<2)
s[stk[pos[u]].size()==2][stk[pos[v]].size()==2].insert(u);
else{
if(stk[pos[opp(stk[pos[u]][0])]].size()<2)t[0].insert(u);
else if(stk[pos[opp(stk[pos[v]][0])]].size()<2)t[0].insert(u);
else if(pos[opp(stk[pos[u]][0])]==pos[v])t[1].insert(u);
else t[2].insert(u);
}
}
inline void del(int u,int v){
if(u!=stk[pos[u]].back())return;
if(v!=stk[pos[v]].back())return;
if(pos[u]==pos[v])return;
if(u>v)swap(u,v);
if(stk[pos[u]].size()<2 || stk[pos[v]].size()<2)
s[stk[pos[u]].size()==2][stk[pos[v]].size()==2].erase(u);
else{
if(stk[pos[opp(stk[pos[u]][0])]].size()<2)t[0].erase(u);
else if(stk[pos[opp(stk[pos[v]][0])]].size()<2)t[0].erase(u);
else if(pos[opp(stk[pos[u]][0])]==pos[v])t[1].erase(u);
else t[2].erase(u);
}
}
inline void oper(int x,int y){
ax[++cnt]=x,ay[cnt]=y;
if(stk[x].empty())ept.erase(x);
if(stk[y].empty())ept.erase(y);
for(int i=0,u,v;i<(int)stk[x].size();++i){
u=stk[x][i],v=opp(u);
del(u,v);
if(stk[pos[v]].size()==2){
u=stk[pos[v]].back(),v=opp(u);
del(u,v);
}
}
for(int i=0,u,v;i<(int)stk[y].size();++i){
u=stk[y][i],v=opp(u);
del(u,v);
if(stk[pos[v]].size()==2){
u=stk[pos[v]].back(),v=opp(u);
del(u,v);
}
}
pos[stk[x].back()]=y;
stk[y].push_back(stk[x].back());
stk[x].pop_back();
if(stk[x].empty())ept.insert(x);
if(stk[y].empty())ept.insert(y);
for(int i=0,u,v;i<(int)stk[x].size();++i){
u=stk[x][i],v=opp(u);
ins(u,v);
if(stk[pos[v]].size()==2){
u=stk[pos[v]].back(),v=opp(u);
ins(u,v);
}
}
for(int i=0,u,v;i<(int)stk[y].size();++i){
u=stk[y][i],v=opp(u);
ins(u,v);
if(stk[pos[v]].size()==2){
u=stk[pos[v]].back(),v=opp(u);
ins(u,v);
}
}
}
inline bool work(int u){
if(ept.empty())return 0;
int t=*ept.begin();
oper(pos[u],t),oper(pos[u+n],t);
return 1;
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=m;++i)stk[i].clear();
for(int i=1;i<=n;++i)vis[i]=0;
for(int i=1,k;i<=m;++i){
scanf("%d",&k);
stk[i].resize(k);
for(int j=0,x;j<k;++j){
scanf("%d",&x);
if(vis[x])x+=n;
else vis[x]=1;
stk[i][j]=x,pos[x]=i;
}
}
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)s[i][j].clear();
for(int i=0;i<3;++i)t[i].clear();
ept.clear();
for(int i=1,u,v;i<=m;++i){
if(stk[i].empty()){
ept.insert(i);
continue;
}
u=stk[i].back(),v=opp(u);
if(stk[pos[v]].back()==v)ins(u,v);
}
cnt=0,ans=1;
while(1){
bool fg=0;
for(int i=0;i<2;++i){
for(int j=0,u;j<2;++j){
if(s[i][j].empty())continue;
u=*s[i][j].begin();
if(stk[pos[u]].size()==1)oper(pos[u+n],pos[u]);
else oper(pos[u],pos[u+n]);
fg=1;break;
}
if(fg)break;
}
if(fg)continue;
for(int i=0;i<3;++i){
if(t[i].empty())continue;
if(work(*t[i].begin())){fg=1;break;}
else{fg=0;break;}
}
if(!fg)break;
}
bool ok=0;
for(int i=1;i<=m;++i){
if(stk[i].size()==1)ans=0;
if(stk[i].size()==2 && stk[i][0]!=opp(stk[i][1]))ok=1;
}
if(!ans){puts("-1");continue;}
if(ok){
for(int i=1;i<=m;++i){
if(stk[i].empty())continue;
if(stk[i].size()!=2)return 0;
if(stk[i][0]==opp(stk[i][1]))continue;
if(ept.empty()){ans=0;break;}
oper(i,*ept.begin());
while(1){
bool fg=0;
for(int i=0;i<2;++i){
for(int j=0,u;j<2;++j){
if(s[i][j].empty())continue;
u=*s[i][j].begin();
if(stk[pos[u]].size()==1)oper(pos[u+n],pos[u]);
else oper(pos[u],pos[u+n]);
fg=1;break;
}
if(fg)break;
}
if(!fg)break;
}
}
}
if(!ans){puts("-1");continue;}
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i)
printf("%d %d\n",ax[i],ay[i]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 11016kb
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 2 1 0 -1
result:
ok 3 cases passed. max #moves/#balls = 1.500000000
Test #2:
score: 0
Accepted
time: 0ms
memory: 9368kb
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 2 1 1 3 1 1 2 1 0 0 0
result:
ok 6 cases passed. max #moves/#balls = 1.000000000
Test #3:
score: 0
Accepted
time: 1ms
memory: 9252kb
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 ...
output:
2 4 1 3 2 2 4 1 5 2 2 4 2 6 5 2 3 2 4 1 2 5 1 4 3 2 5 3 6 1 2 4 1 3 2 2 4 3 5 2 2 6 1 4 3 2 1 2 3 1 2 1 2 4 1 2 4 3 4 1 2 2 1 3 2 2 2 1 3 2 2 1 3 4 1 -1 3 2 1 3 1 3 2 3 2 1 4 1 4 2 -1 3 1 3 2 1 2 3 3 1 3 2 1 2 3 1 3 2 1 4 3 1 4 1 0 0 0
result:
ok 27 cases passed. max #moves/#balls = 1.500000000
Test #4:
score: 0
Accepted
time: 3ms
memory: 8384kb
input:
3 6 1 1 1 2 1 2 1 3 1 3 1 1 3 7 1 3 0 1 2 1 2 1 1 1 1 1 3 3 8 0 1 3 1 2 0 1 1 1 1 1 2 1 3 3 6 1 3 1 3 1 2 1 1 1 1 1 2 3 7 1 1 1 3 1 1 1 2 1 2 1 3 0 3 8 1 1 1 2 0 1 3 1 2 0 1 3 1 1 3 6 1 3 1 1 1 2 1 3 1 2 1 1 3 7 1 1 1 2 0 1 1 1 3 1 3 1 2 3 8 1 2 1 1 1 3 1 2 0 1 3 0 1 1 3 6 1 2 1 2 1 3 1 1 1 1 1 3 3 ...
output:
3 6 1 3 2 5 4 3 6 5 4 3 7 1 3 6 5 7 3 8 2 3 5 4 6 3 2 1 3 3 1 5 4 6 2 3 8 1 5 2 7 4 3 6 2 5 3 4 1 3 4 1 7 2 6 5 3 8 2 4 1 6 3 3 5 4 2 1 6 3 3 5 2 7 4 6 3 3 4 3 2 1 8 5 3 6 1 5 2 4 3 3 6 5 3 1 7 4 3 7 6 5 2 8 4 3 2 1 6 3 5 4 3 3 1 6 5 7 2 3 7 3 4 2 8 6 3 5 1 6 4 3 2 3 7 4 5 1 3 2 3 6 1 7 5 8 4 3 6 4 ...
result:
ok 180 cases passed. max #moves/#balls = 1.333333333
Test #5:
score: 0
Accepted
time: 3ms
memory: 8392kb
input:
4 8 1 3 1 3 1 4 1 1 1 2 1 1 1 4 1 2 4 9 1 3 0 1 2 1 1 1 4 1 1 1 4 1 2 1 3 4 10 1 1 1 3 1 3 1 2 1 2 0 1 1 1 4 1 4 0 4 8 1 4 1 3 1 2 1 2 1 1 1 4 1 1 1 3 4 9 1 4 1 3 1 1 1 3 1 4 1 2 1 1 1 2 0 4 10 1 4 1 1 1 2 1 3 0 0 1 2 1 1 1 3 1 4 4 8 1 2 1 4 1 3 1 4 1 2 1 3 1 1 1 1 4 9 1 1 1 4 1 3 1 2 1 3 1 2 0 1 4 ...
output:
4 6 4 8 5 2 1 7 3 4 6 4 8 3 9 1 7 5 4 7 1 5 4 3 2 9 8 4 7 5 4 3 8 2 6 1 4 7 3 8 6 4 2 5 1 4 8 2 7 3 9 4 10 1 4 8 7 5 1 6 3 4 2 4 9 1 6 4 5 3 8 2 4 7 4 3 2 10 8 6 5 4 3 1 7 4 8 2 6 5 4 9 2 7 1 6 5 4 3 4 10 2 9 1 5 4 8 3 4 5 2 3 1 8 4 7 6 4 5 1 8 3 9 4 7 2 4 6 3 9 2 7 5 8 1 4 8 2 7 6 5 1 4 3 4 8 2 7 6...
result:
ok 1575 cases passed. max #moves/#balls = 1.500000000
Test #6:
score: 0
Accepted
time: 50ms
memory: 8960kb
input:
5 10 1 1 1 4 1 2 1 4 1 5 1 2 1 3 1 5 1 1 1 3 5 11 1 1 1 3 1 1 1 2 1 5 1 2 0 1 5 1 4 1 3 1 4 5 12 1 2 0 1 1 1 5 1 2 1 4 1 3 1 4 0 1 5 1 3 1 1 5 10 1 3 1 5 1 1 1 1 1 2 1 4 1 4 1 5 1 2 1 3 5 11 1 3 1 5 1 2 1 2 1 4 1 3 1 1 1 1 0 1 4 1 5 5 12 1 3 1 4 1 2 0 1 5 1 1 1 2 1 1 1 4 1 5 0 1 3 5 10 1 4 1 5 1 3 1...
output:
5 9 1 6 3 10 7 4 2 8 5 5 3 1 6 4 10 2 11 9 8 5 5 12 3 5 1 11 7 8 6 10 4 5 4 3 9 5 10 1 7 6 8 2 5 8 7 4 3 6 1 10 5 11 2 5 8 6 7 3 12 1 9 2 10 5 5 7 4 9 8 10 3 5 1 6 2 5 4 2 6 1 7 5 9 8 11 3 5 7 1 3 2 11 10 9 8 5 4 5 10 8 5 4 7 6 9 2 3 1 5 7 6 11 1 5 4 3 2 9 8 5 6 2 11 4 9 8 7 1 10 3 5 8 7 10 1 5 4 9 ...
result:
ok 17010 cases passed. max #moves/#balls = 1.400000000
Test #7:
score: 0
Accepted
time: 52ms
memory: 8380kb
input:
6 11 1 5 1 6 1 2 1 4 1 1 1 5 1 4 1 3 1 6 2 2 3 1 1 6 9 1 6 2 1 1 2 4 4 1 2 2 6 2 0 2 5 3 0 2 5 3 6 6 2 4 4 2 5 6 2 3 6 2 2 2 2 3 5 2 1 1 6 8 2 2 1 2 3 4 1 6 2 1 2 2 3 5 0 1 6 2 4 5 6 9 1 6 1 4 1 3 1 5 2 3 1 2 4 2 2 2 1 1 6 1 5 6 7 1 4 2 2 3 2 1 6 2 1 4 2 6 2 2 5 5 1 3 6 8 1 2 2 3 5 1 1 2 4 4 0 2 5 1...
output:
6 11 5 7 4 6 1 9 2 10 8 10 3 5 5 4 5 1 7 5 9 5 9 7 -1 8 7 3 5 6 8 6 2 8 5 2 1 5 4 1 4 5 7 9 4 8 1 5 8 7 8 5 3 6 7 6 2 5 4 1 2 7 5 2 3 5 4 3 5 6 3 7 1 8 7 2 6 8 2 5 9 1 6 2 10 3 7 5 11 8 6 1 6 5 1 3 5 4 5 2 4 3 2 -1 6 12 7 3 2 11 1 10 5 8 6 9 4 3 7 6 5 7 5 3 8 1 2 7 2 9 1 4 7 4 3 5 4 8 4 8 5 6 9 5 14...
result:
ok 14285 cases passed. max #moves/#balls = 1.500000000
Test #8:
score: 0
Accepted
time: 54ms
memory: 8248kb
input:
7 10 2 4 3 1 1 2 2 2 2 4 3 2 7 7 2 6 6 2 5 5 0 1 1 0 7 12 1 2 1 6 1 6 1 5 2 4 1 1 1 2 4 3 1 7 1 5 1 3 1 2 1 7 7 15 1 4 1 6 1 2 1 4 1 6 1 5 1 7 1 1 1 3 0 1 7 1 5 1 1 1 3 1 2 7 7 2 7 3 2 2 3 2 5 7 2 1 1 2 6 6 2 2 5 2 4 4 7 12 2 3 2 1 7 2 6 3 1 4 1 2 1 5 1 1 1 4 1 5 1 1 1 6 1 7 7 14 2 3 5 0 1 2 1 6 1 4...
output:
4 9 2 1 8 4 8 4 1 7 11 1 9 4 3 2 12 8 5 6 7 10 7 5 7 13 8 15 3 14 9 4 1 12 6 5 2 11 7 -1 7 10 7 8 4 9 6 12 2 1 5 3 1 11 3 7 13 10 14 3 8 5 12 4 11 9 1 7 6 1 7 6 1 3 2 10 2 7 3 8 10 4 8 7 4 7 12 5 10 7 9 8 4 1 2 11 6 2 6 3 7 10 2 6 4 5 11 3 1 7 1 5 3 9 7 7 7 2 9 5 4 1 6 4 8 6 10 6 10 8 7 5 4 8 3 9 2 ...
result:
ok 12500 cases passed. max #moves/#balls = 1.428571429
Test #9:
score: 0
Accepted
time: 59ms
memory: 8924kb
input:
8 16 1 2 0 1 5 1 8 1 1 1 5 2 4 4 1 8 1 6 1 1 1 2 0 2 7 7 1 3 1 6 1 3 8 13 1 8 1 4 1 2 1 6 2 1 3 2 1 3 1 7 1 2 1 5 1 6 1 8 2 4 5 1 7 8 9 2 1 3 2 4 5 2 7 2 2 7 8 2 4 8 2 1 6 2 5 2 2 6 3 0 8 17 1 1 1 4 1 3 1 7 1 2 1 2 1 7 1 5 1 3 1 4 1 6 1 8 1 5 1 6 1 8 1 1 0 8 15 1 6 1 4 0 1 5 1 7 1 3 1 2 1 8 1 6 1 7 ...
output:
6 10 5 11 1 16 14 6 3 15 9 8 4 9 8 3 10 4 13 7 11 1 12 9 12 2 5 8 6 8 6 5 -1 8 16 1 6 5 9 3 10 2 13 8 14 11 7 4 15 12 9 15 7 14 6 9 1 10 5 12 8 11 3 13 3 11 2 13 4 9 8 1 9 1 2 8 9 2 3 9 7 9 4 3 5 7 5 4 7 6 2 1 6 8 6 10 1 4 10 5 8 5 4 8 9 7 11 2 16 4 8 3 12 10 13 5 6 1 15 14 10 8 5 3 8 7 8 4 3 7 4 1 ...
result:
ok 11111 cases passed. max #moves/#balls = 1.500000000
Test #10:
score: 0
Accepted
time: 50ms
memory: 11664kb
input:
9 13 1 2 2 4 5 2 5 4 2 2 9 1 8 1 3 1 1 1 3 1 1 2 7 6 1 9 1 8 2 7 6 9 13 1 4 2 5 6 2 7 5 2 9 3 1 4 2 9 7 0 2 8 6 2 1 3 0 1 2 1 2 2 8 1 9 18 1 4 1 7 1 7 1 9 1 8 1 8 1 2 1 3 1 6 1 2 1 1 1 3 1 5 1 1 1 6 1 5 1 4 1 9 9 13 0 2 6 7 2 2 2 1 3 2 6 8 2 9 1 2 1 4 1 9 2 8 7 0 1 4 1 3 2 5 5 9 17 1 9 2 1 3 1 2 1 5...
output:
11 9 7 8 6 12 5 4 11 4 1 10 4 13 4 13 10 2 8 3 2 3 8 11 12 11 5 1 4 5 9 5 13 9 2 7 8 7 13 8 3 2 6 3 6 4 9 14 11 10 7 12 8 17 1 16 13 15 9 3 2 6 5 18 4 8 12 4 7 11 6 7 8 6 2 1 9 1 5 9 5 2 9 11 3 10 4 17 9 16 15 14 5 13 1 2 7 6 12 6 2 13 1 3 10 3 10 1 5 4 6 4 9 6 9 5 2 9 8 2 8 9 7 8 11 7 11 8 8 12 5 1...
result:
ok 10000 cases passed. max #moves/#balls = 1.444444444
Test #11:
score: 0
Accepted
time: 48ms
memory: 10072kb
input:
10 19 1 1 1 3 1 10 1 8 1 1 1 4 1 2 1 2 1 5 1 7 1 5 2 6 6 1 7 1 3 1 4 1 9 1 10 1 8 1 9 10 19 1 8 1 10 2 7 7 1 2 1 5 1 9 1 1 0 1 6 1 9 1 1 1 6 1 5 0 1 2 1 10 2 4 4 2 3 3 1 8 10 10 2 5 5 2 2 3 2 8 4 2 2 7 2 6 9 2 3 10 2 10 1 2 6 4 2 7 8 2 9 1 10 19 1 4 1 5 1 4 1 9 2 3 9 1 10 1 1 1 7 1 6 1 8 1 10 1 5 1 ...
output:
9 5 1 8 7 14 2 15 6 11 9 13 10 18 4 19 16 17 3 7 11 7 15 4 13 5 12 9 19 1 10 6 16 2 -1 10 17 7 16 13 3 1 12 2 14 9 18 8 15 10 11 6 5 4 19 5 11 19 4 12 10 16 15 17 3 9 1 14 8 5 6 13 5 7 2 18 7 18 2 7 16 8 18 12 13 6 14 10 3 1 19 17 9 5 10 16 9 6 4 12 8 14 7 17 10 15 2 18 11 3 13 5 3 5 1 10 12 8 13 10...
result:
ok 9090 cases passed. max #moves/#balls = 1.500000000
Test #12:
score: 0
Accepted
time: 53ms
memory: 14448kb
input:
11 15 2 11 11 2 3 3 1 2 0 2 8 5 1 2 2 6 4 2 4 5 1 1 1 1 1 9 1 10 2 8 6 2 7 7 2 9 10 11 17 2 4 8 1 11 2 6 7 1 9 1 9 1 5 1 2 1 2 1 5 1 10 1 3 1 1 1 11 2 10 8 1 1 2 3 7 2 4 6 11 21 1 10 1 6 1 3 1 9 1 8 1 1 1 5 1 10 1 5 1 4 1 8 1 9 1 11 1 6 1 11 1 7 1 1 1 4 2 2 2 1 7 1 3 11 15 1 5 1 1 1 2 2 3 3 2 10 7 0...
output:
9 10 9 6 3 15 12 15 11 5 4 8 4 7 8 13 7 13 5 13 15 12 8 7 9 6 5 4 13 2 3 5 16 5 16 11 17 3 1 8 14 8 17 1 14 10 10 17 6 21 3 18 10 9 7 14 2 20 16 11 5 12 4 8 1 15 13 11 9 2 10 1 15 3 12 11 8 12 15 8 13 6 14 6 7 14 5 7 13 5 10 10 7 18 14 6 3 17 12 15 4 19 2 13 9 16 8 5 11 16 5 11 7 10 12 7 1 12 4 12 3...
result:
ok 8333 cases passed. max #moves/#balls = 1.363636364
Test #13:
score: -100
Wrong Answer
time: 55ms
memory: 11964kb
input:
12 25 1 9 1 10 1 4 1 7 1 5 1 3 1 6 1 1 1 12 1 3 1 2 1 9 1 11 1 2 0 1 10 1 7 1 12 1 11 1 4 1 6 1 5 1 1 1 8 1 8 12 19 1 2 1 12 2 8 8 2 1 3 0 2 3 4 1 5 2 11 11 2 1 5 2 9 6 1 12 1 7 1 7 2 6 9 1 2 1 4 1 10 1 10 0 12 14 2 2 4 2 8 8 2 1 3 2 9 9 2 6 12 2 6 1 0 2 10 10 2 5 5 2 3 12 0 2 4 7 2 7 2 2 11 11 12 1...
output:
12 23 8 14 11 10 6 20 3 22 5 21 7 17 4 25 24 12 1 16 2 19 13 18 9 11 15 1 13 12 18 17 11 2 9 7 6 16 4 6 9 4 10 5 14 10 14 5 9 5 7 10 7 3 10 6 3 6 5 1 6 13 1 12 13 12 6 10 8 5 14 5 3 8 1 3 7 13 12 13 7 1 4 12 6 4 14 6 12 24 11 14 7 19 5 10 1 21 12 25 16 6 2 20 4 22 8 17 9 13 3 18 15 11 12 2 5 4 8 5 1...
result:
wrong answer Should find solution [Case 5542]