QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792412#3040. ContainerCorydoRE 0ms0kbC++142.1kb2024-11-29 10:05:042024-11-29 10:05:04

Judging History

你现在查看的是最新测评结果

  • [2024-11-29 10:05:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-29 10:05:04]
  • 提交

answer

#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1e3+3;
int n,C,f[N][N],a[N],b[N],c[N],mh[N],p0[N],p1[N],m,m1,m2;
vector<pii>vec;
inline int c1(int i,int j){
	if(j>=m1)return 1<<30;
	return (C+4)*(abs(a[i]-b[j+1])>>1)+(a[i]&1?max(0,i-j-1-p0[b[j+1]]):C+3);
}
inline int c2(int i,int j){
	if(i-j>m2)return 1<<30;
	return (C+4)*(abs(a[i]-c[i-j])>>1)+(a[i]&1?C+3:max(0,j-p1[c[i-j]]));
}
int d[N];
inline void ins(int l,int r){
	if(l>r)swap(l,r);
	vec.pb(P(l,r));
	swap(d[l],d[r]);
}
inline void mov(int l,int r){
	if(l==r)return ;
	if(abs(r-l)==1){ins(l,r);return ;}
	int p=l<r?2:-2;
	if(d[l+p])mov(l+p,r),ins(l,l+p);
	else ins(l,l+p),mov(l+p,r);
}
int main() {
    freopen("machine.in", "r", stdin);
    freopen("machine.out","w",stdout);
	read(),n=read(),C=read();
	static char s[N];
	scanf("%s",s+1); rep(i,1,n)if(s[i]=='B')a[++m]=i;
	scanf("%s",s+1); rep(i,1,n)if(s[i]=='B')(i&1?b[++m1]:c[++m2])=i;
	rep(i,1,m1)p1[b[i]]=1;rep(i,1,n)p1[i]+=p1[i-1];
	rep(i,1,m2)p0[c[i]]=1;rep(i,1,n)p0[i]+=p0[i-1];
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	rep(i,1,m)rep(j,0,i-1){
		f[i][j+1]=min(f[i][j+1],f[i-1][j]+c1(i,j));
		f[i][j]=min(f[i][j],f[i-1][j]+c2(i,j));
	}
	int ans=f[m][m1];
	int p;
	rep(j,0,m)if(f[m][j]==ans){p=j;break;}
	per(i,m,1){
		if(p&&f[i-1][p-1]+c1(i,p-1)==f[i][p]) mh[b[p--]]=a[i];
		else mh[c[i-p]]=a[i];
	}
	//rep(i,1,m)printf("%d %d\n",a[i],mh[i]);
	rep(i,1,m)d[a[i]]=1;
	per(i,n,1)if(mh[i]&&mh[i]<i)mov(mh[i],i);
	rep(i,1,n)if(mh[i]&&mh[i]>i)mov(mh[i],i);
	printf("%ld\n",vec.size());
	for(pii A:vec)printf("%d %d\n",A.fi,A.se);
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

5 2
11221
21112

output:


result: