QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #288260 | #5446. 琪露诺的符卡交换 | catagory# | 20 | 463ms | 7468kb | C++23 | 7.0kb | 2023-12-22 12:14:31 | 2024-07-04 03:14:43 |
Judging History
answer
#include<bits/stdc++.h>
#define LL int
#define SZ(x) ((LL)(x.size()))
using namespace std;
inline int read(){
int q=0,w=1;
char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
return q*w;
}
void write(LL x){
if(x<0){putchar('-');x=(-x);}
if(x>9)write(x/10);
putchar('0'+x%10);
}
inline void writeln(LL x){write(x);puts("");}
inline void writecs(LL x){write(x);putchar(' ');}
inline void lsh(vector<LL>&vc){
sort(vc.begin(),vc.end(),[&](LL x,LL y){return x<y;});
vc.erase(unique(vc.begin(),vc.end()),vc.end());
return ;
}
namespace dinic{
const int N = 100000+95 , M = 500000+95;
LL n,s,t;
struct Edge{
LL to,nxt,w,c;
}e[M<<1];LL head[N],tot=1,cur[N];
inline void add(LL u,LL v,LL w,LL c){
e[++tot].to=v;e[tot].nxt=head[u];
e[tot].w=w;e[tot].c=c;head[u]=tot;return ;
}
inline void add_e(LL u,LL v,LL w,LL c){
add(u,v,w,c);add(v,u,0,-c);
}
inline void clear(){
for(LL i=1;i<=n;i++)head[i]=cur[i]=0;
n=s=t=0;tot=1;return ;
}
LL dis[N];bool vis[N];
inline bool spfa(){
for(LL i=1;i<=n;i++){dis[i]=(LL)(1e18);cur[i]=head[i];}
queue<LL>q;q.push(s);dis[s]=0;vis[s]=1;
while(!q.empty()){
LL x=q.front();q.pop();vis[x]=0;
for(LL i=head[x];i;i=e[i].nxt)
if(dis[e[i].to]>dis[x]+e[i].c&&e[i].w){
dis[e[i].to]=dis[x]+e[i].c;
if(!vis[e[i].to]){q.push(e[i].to);vis[e[i].to]=1;}
}
}
return (dis[t]!=(LL)(1e18));
}
bool inq[N];
LL dfs(LL x,LL flow){
if(x==t)return flow;
inq[x]=1;LL lastflow=flow;
for(LL i=cur[x];i&&flow;i=e[cur[x]].nxt){
cur[x]=i;
if(dis[e[i].to]==dis[x]+e[i].c&&e[i].w&&!inq[e[i].to]){
LL d=dfs(e[i].to,min(flow,e[i].w));
if(d){e[i].w-=d;e[i^1].w+=d;flow-=d;}
}
}
inq[x]=0;
if(lastflow==flow)dis[x]=(LL)(1e18);
return lastflow-flow;
}
inline LL solve(){
LL maxflow=0,mincost=0;
while(spfa()){
LL d=dfs(s,(LL)(1e18));
maxflow+=d;
mincost+=d*dis[t];
}
return maxflow;
}
}
namespace TP{
const int N = 200+95;
LL lim;vector<LL>E[N];LL matchL[N],matchR[N];
inline void clear(){
for(LL i=1;i<=lim;i++){E[i].clear();matchL[i]=matchR[i]=0;}
return ;
}
inline void add_e(LL x,LL y){E[x].push_back(y);return ;}
bool vis[N];
bool dfs(LL x){
if(vis[x])return 0;
vis[x]=1;
for(auto y:E[x]){
if(!matchR[y]){matchL[x]=y;matchR[y]=x;return 1;}
if(dfs(matchR[y])){matchL[x]=y;matchR[y]=x;return 1;}
}
return 0;
}
inline void solve(LL CNT=-1){
LL cnt=0;
for(LL t=1;t<=lim;t++){
for(LL x=1;x<=lim;x++)vis[x]=0;
cnt+=dfs(t);
}
if(CNT!=-1)assert(CNT==cnt);
return ;
}
}
#define x1 x_tmp_1
#define y1 y_tmp_1
struct pt{LL x,y;};
const int N = 200+5;
int T,n;vector<pt>a[N][N];bool b[N][N];vector<vector<LL>>ans;LL __c[N][N];
inline void make(LL x0,LL y0,LL x1,LL y1){
// cout<<" x0 = "<<x0<<" y0 = "<<y0<<" x1 = "<<x1<<" y1 = "<<y1<<endl;
if(x0==x1&&y0==y1){
assert(SZ(a[x0][y0])&&!b[x0][y0]);
a[x0][y0].pop_back();
b[x0][y0]=1;return ;
}
assert(SZ(a[x0][y0])&&SZ(a[x1][y1])&&!b[x0][y1]&&!b[x1][y0]);
pt X=a[x0][y0].back();a[x0][y0].pop_back();
pt Y=a[x1][y1].back();a[x1][y1].pop_back();
b[x0][y1]=b[x1][y0]=1;
ans.push_back({X.x,X.y,Y.x,Y.y});
return ;
}
#define PLL pair<LL,LL>
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second
#define random(a,b) (rand()%(b-a+1)+a)
vector<LL>vec[N*N*N];LL top;
int main(){
random_device seed;srand(seed());
T=read();
while(T--){
ans.clear();
/* n=random(200,200);
for(LL i=1;i<=n;i++)
for(LL j=1;j<=n;j++)__c[i][j]=i;*/
/* while(true){
LL v=random(0,10);
cerr<<" v = "<<v<<endl;
if(v==0)break;
LL x0=random(1,n),y0=random(1,n);
LL x1=random(1,n),y1=random(1,n);
swap(__c[x0][y0],__c[x1][y1]);
}*/
n=read();
for(LL i=1;i<=n;i++)
for(LL j=1;j<=n;j++)__c[i][j]=read();
/* cout<<n<<endl;
for(LL i=1;i<=n;i++){
for(LL j=1;j<=n;j++)cout<<__c[i][j]<<" ";
cout<<endl;
}*/
TP::lim=n;
for(LL i=1;i<=n;i++)
for(LL j=1;j<=n;j++){a[i][j].clear();b[i][j]=0;}
for(LL i=1;i<=n;i++)
for(LL j=1;j<=n;j++){a[i][__c[i][j]].push_back((pt){i,j});}
vector<LL>idxL(n+2),idxR(n+2);LL Id=0,S=0,T=0;
vector<vector<LL>>idL(n+2),idR(n+2);
S=++Id;T=++Id;
for(LL i=1;i<=n;i++){
idxL[i]=++Id;idL[i].resize(n+2);
for(LL j=1;j<=n;j++)idL[i][j]=++Id;
}
for(LL i=1;i<=n;i++){
idxR[i]=++Id;idR[i].resize(n+2);
for(LL j=1;j<=n;j++)idR[i][j]=++Id;
}
for(LL t=1;t<=n;t++){
// cout<<"> t = "<<t<<" clock() = "<<clock()<<endl;
dinic::clear();dinic::n=Id;dinic::s=S;dinic::t=T;
for(LL i=1;i<=n;i++){
if(!SZ(a[i][t]))continue;
dinic::add_e(S,idxL[i],SZ(a[i][t]),0);
for(LL k=1;k<=n;k++)
if((!b[i][k]))dinic::add_e(idxL[i],idL[i][k],1,0);
}
for(LL j=1;j<=n;j++){
if(b[j][t])continue;
dinic::add_e(idxR[j],T,1,0);
for(LL k=1;k<=n;k++)
if(SZ(a[j][k]))dinic::add_e(idR[j][k],idxR[j],1,k);
}
top=0;
for(LL i=1;i<=n;i++)
if(SZ(a[i][t]))
for(LL j=1;j<=n;j++)
for(LL k=(t+1);k<=n;k++)
if((!b[i][k])&&(SZ(a[j][k]))){
vec[top]={dinic::tot+1,i,j,k};top++;
dinic::add_e(idL[i][k],idR[j][k],1,0);
}
for(LL i=1;i<=n;i++){
vec[top]={dinic::tot+1,i,i,t};top++;
dinic::add_e(idxL[i],idxR[i],1,0);
}
LL cnt=0;
for(LL i=1;i<=n;i++)
if(!b[i][t])cnt++;
LL maxflow=dinic::solve();
assert(cnt==maxflow);
for(LL i=0;i<top;i++)
if(!dinic::e[vec[i][0]].w)
make(vec[i][1],t,vec[i][2],vec[i][3]);
/* cout<<" ----------> "<<endl;
for(LL i=1;i<=n;i++){
for(LL j=1;j<=n;j++)cout<<SZ(a[i][j])<<" ";
cout<<endl;
}
cout<<" ------ "<<endl;
for(LL i=1;i<=n;i++){
for(LL j=1;j<=n;j++)cout<<b[i][j]<<" ";
cout<<endl;
}
cout<<endl;*/
}
writeln(SZ(ans));
for(LL t=0;t<SZ(ans);t++){
for(LL i=0;i<SZ(ans[t]);i++)writecs(ans[t][i]);
puts("");
}
for(LL t=0;t<SZ(ans);t++){
LL x0=ans[t][0],y0=ans[t][1],x1=ans[t][2],y1=ans[t][3];
swap(__c[x0][y0],__c[x1][y1]);
}
for(LL t=1;t<=n;t++){
vector<LL>vec(n);
for(LL i=1;i<=n;i++)vec[i-1]=__c[t][i];
lsh(vec);assert(SZ(vec)==n);
}
}
return 0;
}
/*
my test data:
1
4
1 1 1 2
2 2 2 4
3 3 3 1
4 4 4 3
1
8
1 1 1 1 1 1 1 6
2 2 2 2 2 2 2 5
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 8
5 5 5 5 5 5 5 1
6 6 6 6 6 6 6 7
7 7 7 7 7 7 7 4
8 8 8 8 8 8 8 2
1
10
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 8
3 3 3 3 3 3 3 3 3 4
4 4 4 4 4 4 4 4 4 6
5 5 5 5 5 5 5 5 5 9
6 6 6 6 6 6 6 6 6 2
7 7 7 7 7 7 7 7 7 3
8 8 8 8 8 8 8 8 8 10
9 9 9 9 9 9 9 9 9 7
10 10 10 10 10 10 10 10 10 5
1
5
1 4 2 1 3
1 5 5 2 2
3 3 3 4 2
3 4 1 4 4
5 2 5 5 1
*/
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 165ms
memory: 6676kb
input:
7 132 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 ...
output:
8646 59 132 1 132 59 131 2 132 59 130 3 132 59 129 4 132 59 128 5 132 59 127 6 132 59 126 7 132 59 125 8 132 59 124 9 132 59 123 10 132 59 122 11 132 59 121 12 132 59 120 13 132 59 119 14 132 59 118 15 132 59 117 16 132 59 116 17 132 59 115 18 132 59 114 19 132 59 113 20 132 59 1...
result:
ok your solution is correct.
Test #2:
score: 0
Accepted
time: 54ms
memory: 6480kb
input:
8 14 13 13 13 13 13 13 13 13 13 13 13 13 13 13 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 14 14 14 14 14 14 14 14 14 14 14 14 14 14 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 10 10 10 10 10 10 10 10 10 10 10 10 10 2 2 2 2 2 2 2 2 2 2 2 2 2 2 9...
output:
91 7 14 1 14 7 13 2 14 7 12 3 14 7 11 4 14 7 10 5 14 7 9 6 14 7 8 8 14 7 7 9 14 7 6 10 14 7 5 11 14 7 4 12 14 7 3 13 14 7 2 14 14 9 13 1 13 9 12 2 13 9 11 3 13 9 10 4 13 9 9 5 13 9 8 6 13 9 7 8 13 9 6 10 13 9 5 11 13 9 4 12 13 9 3 13 13 9 2 14 13 13 12 1 12 13 11 2 12 13 1...
result:
ok your solution is correct.
Test #3:
score: 0
Accepted
time: 88ms
memory: 6336kb
input:
4 82 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...
output:
3321 56 82 1 82 56 81 2 82 56 80 3 82 56 79 4 82 56 78 5 82 56 77 6 82 56 76 7 82 56 75 8 82 56 74 9 82 56 73 10 82 56 72 11 82 56 71 12 82 56 70 13 82 56 69 14 82 56 68 15 82 56 67 16 82 56 66 17 82 56 65 18 82 56 64 19 82 56 63 20 82 56 62 21 82 56 61 22 82 56 60 23 82 56 59...
result:
ok your solution is correct.
Test #4:
score: 0
Accepted
time: 463ms
memory: 7468kb
input:
8 3 1 1 1 3 3 3 2 2 2 3 1 1 1 3 3 3 2 2 2 1 1 11 5 5 5 5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 4 4 4 4 4 4 4 4 4 4 4 11 11 11 11 11 11 11 11 11 11 11 2 2 2 2 2 2 2 2 2 2 2 6 6 6 6 6 6 6 6 6 6 6 8 8 8 8 8 8 8 8 8 8 8 10 10 10 10 10 10 10 10 10 10 10 7 7 7 7 7...
output:
3 1 3 2 3 1 2 3 3 3 2 2 2 3 1 3 2 3 1 2 3 3 3 2 2 2 0 55 3 11 1 11 3 10 2 11 3 9 4 11 3 8 5 11 3 7 6 11 3 6 7 11 3 5 8 11 3 4 9 11 3 3 10 11 3 2 11 11 7 10 1 10 7 9 2 10 7 8 4 10 7 7 5 10 7 6 6 10 7 5 8 10 7 4 9 10 7 3 10 10 7 2 11 10 2 9 1 9 2 8 4 9 2 7 5 9 2 6 6 9 2 5 ...
result:
ok your solution is correct.
Subtask #2:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #5:
score: 0
Runtime Error
input:
5 17 9 9 9 9 9 9 9 9 9 9 9 9 9 2 9 9 9 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 2 2 2 2 2 2 2 2 2 2 2 2 11 2 2 2 2 4 4 4 4 4 4 10 4 4 4 4 4 4 4 4 4 4 10 10 10 10 10 10 8 10 10 10 10 10 10 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 14 12 12 12 12 14 14 14 14 14 14 14 14 14 14 14 12 14 14 14 14 14 16 16...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%