QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#81933 | #2830. Data Structure | AHSFNU_team_0 | WA | 3ms | 13344kb | C++14 | 3.2kb | 2023-02-26 18:37:16 | 2023-02-26 18:37:17 |
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(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(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);
}
for(int i=0,u,v;i<(int)stk[y].size();++i){
u=stk[y][i],v=opp(u);
del(u,v);
}
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);
}
for(int i=0,u,v;i<(int)stk[y].size();++i){
u=stk[y][i],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(i==1 && j==1)continue;
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;
}
for(int i=1;i<=m;++i){
if(stk[i].size()==0)continue;
if(stk[i].size()==1)ans=0;
if(stk[i].size()==2 && stk[i][0]!=opp(stk[i][1]))ans=0;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 12636kb
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: 3ms
memory: 13344kb
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: -100
Wrong Answer
time: 2ms
memory: 13124kb
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 -1 -1 1 3 2 1 4 3 1 4 1 0 0 0
result:
wrong answer Should find solution [Case 20]