QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #246322 | #2830. Data Structure | nameless_story# | RE | 1ms | 3536kb | C++20 | 6.0kb | 2023-11-10 19:00:25 | 2023-11-10 19:00:25 |
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()
mt19937 rnd(3456);
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int n,m,i,j;
n=5; m=7;
while (cin>>n>>m)
// int T=1000;
// while (T--)
{
vector<vector<int>> a(m);
vector<int> pos(n);
vector<int> empty;
// for (i=0; i<n; i++)
// {
// int x;
// x=rnd()%m;
// while (a[x].size()==2) x=rnd()%m;
// a[x].push_back(i); pos[i]+=x;
// x=rnd()%m;
// while (a[x].size()==2) x=rnd()%m;
// a[x].push_back(i); pos[i]+=x;
// }
// for (i=0; i<m; i++) if (a[i].size()==0) empty.push_back(i);
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);
}
// cerr<<"__\n";
// for (int i=0; i<m; i++)
// {
// for (int x:a[i]) cerr<<x<<' '; cerr<<endl;
// }
auto b=a;
auto solve=[&]() -> vector<pair<int,int>>
{
vector<int> id(n);
iota(all(id),0);
shuffle(all(id),rnd);
vector<pair<int,int>> ans;
/*auto onesingle=[&](int i)
{
// cerr<<"onesingle "<<i<<endl;
assert(a[i].size()==1);
int x=a[i][0];
int j=pos[x]-i;
assert(a[j].size());
if (a[j].back()==x)
{
ans.push_back({j,i});
a[i]={x,x};
a[j].pop_back();
pos[x]=i*2;
if (!a[j].size()) empty.push_back(j);
return;
}
assert(a[j].size()==2);
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;
};*/
function<void(int)> one=[&](int i)
{
// cerr<<"one "<<i<<endl;
assert(a[i].size()==1);
int x=a[i][0];
int j=pos[x]-i;
assert(a[j].size());
if (a[j].back()==x)
{
ans.push_back({j,i});
a[i]={x,x};
a[j].pop_back();
pos[x]=i*2;
if (!a[j].size()) empty.push_back(j);
if (a[j].size()==1) one(j);
return;
}
assert(a[j].size()==2);
assert(a[j][0]==x);
// assert(empty.size());
if (empty.size()==0) return;
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;
one(v);
return;
};
auto twoup=[&](int i)
{
// cerr<<"twoup "<<i<<endl;
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();
if (a[j][0]!=y)
{
assert((a[j]==vector{x,y}));
ans.push_back({j,v});
ans.push_back({i,j});
ans.push_back({i,v});
pos[x]=j*2;
pos[y]=v*2;
a[i]={ };
a[j]={x,x};
a[v]={y,y};
return;
}
assert((a[j]==vector{y,x}));
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]={ };
empty.push_back(j);
};
auto two=[&](int i)
{
// cerr<<"two "<<i<<endl;
int x=a[i][1];
int j=pos[x]-i;
assert(a[j].size()==2);
int e1=empty.back(); empty.pop_back();
ans.push_back({j,e1});
if (a[j][1]==x)
{
ans.push_back({i,e1});
a[e1]={x,x};
pos[x]=e1*2;
a[i].pop_back(); a[j].pop_back();
one(i);
assert(a[j].size()==0);
return;
}
pos[a[j].back()]+=e1-j;
a[e1]={a[j].back()};
ans.push_back({i,j});
a[j]={x,x};
pos[x]=j*2;
a[i].pop_back();
one(i);
assert(a[e1].size()==0);
};
// for (i=0; i<m&&empty.size()>=2; i++) if (a[i].size()==2&&a[i][0]!=a[i][1]) two(i);
// for (int i:id) if (a[i].size()==1)
// {
// int x=a[i][0];
// if (a[pos[x]-i]==vector{x}) one(i);
// }
for (int i:id) 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)
{
int x=pos[a[i][0]]-i;
int D=a[x][1];
int y=pos[D]-x;
if (a[y].back()==D) one(i);
}
for (i=0; i<m&&empty.size(); i++) if (a[i].size()==1)
{
one(i);
}
if (empty.size()) for (i=0; i<m; i++) assert(a[i].size()!=1);
for (i=0; i<m&&empty.size(); i++) if (a[i].size()==2&&a[i][0]!=a[i][1]&&pos[a[i][0]]==pos[a[i][1]]) twoup(i);
if (empty.size()) for (i=0; i<m; i++) assert(a[i].size()!=1);
for (i=0; i<m&&empty.size()>=2; i++) if (a[i].size()==2&&a[i][0]!=a[i][1]) two(i);
if (empty.size()) for (i=0; i<m; i++) assert(a[i].size()!=1);
for (i=0; i<m; i++) if (a[i].size())
{
if (a[i].size()!=2)
{
assert(empty.size()<2);
return {{-1,-1}};
}
if (a[i][0]!=a[i][1])
{
assert(empty.size()<2);
return {{-1,-1}};
}
}
return ans;
};
auto ans=solve();
if (ans==vector{pair{-1,-1}}) cout<<"-1\n";
else
{
// if (ans.size()>3*n/2)
// {
// cout<<"-1\n";
// continue;
// }
cout<<ans.size()<<'\n';
// assert(ans.size()<=3*n/2);
auto a=b;
for (auto [x,y]:ans)
{
cout<<x+1<<' '<<y+1<<'\n';
assert(a[x].size());
assert(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: 1ms
memory: 3496kb
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: 0
Accepted
time: 0ms
memory: 3536kb
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
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 ...