QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246250 | #2830. Data Structure | nameless_story# | RE | 0ms | 3592kb | C++20 | 3.2kb | 2023-11-10 17:52:25 | 2023-11-10 17:52:26 |
Judging History
answer
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int n,m,i,j;
while (cin>>n>>m)
{
vector<vector<int>> a(m);
vector<int> pos(n);
vector<int> empty;
for (i=0; i<m; i++)
{
int sz;
cin>>sz;
a[i].resize(sz);
for (int &x:a[i])
{
cin>>x;
pos[--x]+=i;
}
if (sz==0) empty.push_back(i);
}
auto b=a;
auto solve=[&]() -> vector<pair<int,int>>
{
vector<pair<int,int>> ans;
auto one=[&](int i)
{
assert(a[i].size()==1);
int x=a[i][0];
int j=pos[x]-i;
assert(a[j].size());
if (a[j].size()==2)
{
if (a[j][1]==x)
{
ans.push_back({j,i});
a[i]={x,x};
a[j].pop_back();
pos[x]=i*2;
return;
}
assert(a[j][0]==x);
assert(empty.size());
int v=empty.back(); empty.pop_back();
ans.push_back({j,v});
ans.push_back({j,i});
empty.push_back(j);
a[v]={a[j][1]};
pos[a[v][0]]+=v-j;
a[j]={ };
a[i]={x,x};
pos[x]=i*2;
return;
}
empty.push_back(j);
ans.push_back({j,i});
a[j]={ };
a[i]={x,x};
pos[x]=i*2;
};
auto twoup=[&](int i)
{
assert(a[i].size()==2&&pos[a[i][0]]==pos[a[i][1]]);
int x=a[i][1],y=a[i][0];
int j=pos[x]-i;
assert(empty.size());
int v=empty.back(); empty.pop_back();
ans.push_back({j,v});
ans.push_back({i,v});
ans.push_back({j,i});
pos[x]=v*2;
pos[y]=i*2;
a[i]={y,y};
a[v]={x,x};
a[j]={ };
};
auto two=[&](int i)
{
int x=a[i][1];
int j=pos[x]-i;
assert(a[j].size()==2&&a[j][0]==x);
int e1=empty.back(); empty.pop_back();
ans.push_back({j,e1});
pos[a[j].back()]+=e1-j;
a[e1]={a[j].back()};
a[j]={x,x};
pos[x]=j*2;
a[i].pop_back();
one(i);
};
for (i=0; i<m; i++) if (a[i].size()==1)
{
int x=a[i][0];
if (a[pos[x]-i].back()==x) one(i);
}
for (i=0; i<m&&empty.size(); i++) if (a[i].size()==1) one(i);
for (i=0; i<m&&empty.size(); i++) if (a[i].size()==2&&pos[a[i][0]]==pos[a[i][1]]) twoup(i);
for (i=0; i<m&&empty.size()>=2; i++) if (a[i].size()==2) two(i);
for (i=0; i<m; i++) if (a[i].size())
{
if (a[i].size()!=2) return {{-1,-1}};
if (a[i][0]!=a[i][1]) return {{-1,-1}};
}
return ans;
};
auto ans=solve();
if (ans==vector{pair{-1,-1}}) cout<<"-1\n";
else
{
cout<<ans.size()<<'\n';
auto a=b;
for (auto [x,y]:ans)
{
cout<<x+1<<' '<<y+1<<'\n';
assert(a[x].size()&&a[y].size()<=1);
if (a[y].size()) assert(a[y][0]==a[x].back());
a[y].push_back(a[x].back()); a[x].pop_back();
}
for (i=0; i<m; i++) if (a[i].size())
{
assert(a[i].size()==2&&a[i][0]==a[i][1]);
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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 2 3 1 3 2 1 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