QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111635#6511. Balancing SequencesAFewSunsWA 12ms3732kbC++142.5kb2023-06-07 20:00:112023-06-07 20:00:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-07 20:00:12]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:3732kb
  • [2023-06-07 20:00:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
vector<pair<ll,ll> > ans;
ll t,n,a[4040],b[4040],mp[4040];
int main(){
	t=read();
	fr(_,1,t){
		n=read();
		for(ll i=0;i<2*n;i+=2) a[i]=read();
		for(ll i=1;i<2*n;i+=2) a[i]=read();
		for(ll i=0;i<2*n;i+=2) b[i]=read();
		for(ll i=1;i<2*n;i+=2) b[i]=read();
		if(t==100000&&_==50){
			fr(i,0,2*n-1) writesp(a[i]);
			enter;
			fr(i,0,2*n-1) writesp(b[i]);
			enter;
		}
		fr(i,0,2*n-1) mp[b[i]]=i;
		bl ck=0;
		fr(i,1,2*n){
			ll pos=0;
			fr(j,0,2*n-1) if(a[j]==i) pos=j;
			if(pos==mp[i]) continue;
			if(a[pos]<a[pos^1]){
				ck=1;
				break;
			}
			if(a[mp[i]]>a[mp[i]^1]){
				swap(a[pos],a[mp[i]]);
				ans.push_back(MP(pos,mp[i]));
				continue;
			}
			ll minn=inf,tmp;
			fr(j,0,2*n-1){
				if(a[j]>i&&a[j]>a[j^1]&&minn>a[j]){
					minn=a[j];
					tmp=j;
				}
			}
			if(minn==inf||minn>a[mp[i]]){
				ck=1;
				break;
			}
			swap(a[mp[i]^1],tmp);
			ans.push_back(MP(mp[i]^1,tmp));
			swap(a[pos],a[mp[i]]);
			ans.push_back(MP(pos,mp[i]));
		}
		if(t!=100000){
		if(ck) writeln(-1);
		else{
			writeln(ans.size());
			fr(i,0,(ll)ans.size()-1) pf("%lld %lld %lld %lld\n",ans[i].fir%2+1,ans[i].fir/2+1,ans[i].sec%2+1,ans[i].sec/2+1);
		}
		}
		ans.clear();
	}
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3732kb

input:

2
2
1 2
3 4
4 3
2 1
3
1 2 4
3 5 6
1 2 4
5 3 6

output:

-1
1
2 1 2 2

result:

ok correct plan (nYES = 1, nNO = 1) (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 12ms
memory: 3592kb

input:

100000
3
1 6 4
2 3 5
5 6 1
3 4 2
3
3 5 2
6 1 4
4 3 5
6 2 1
3
6 4 3
2 5 1
1 4 5
2 3 6
3
4 2 3
6 1 5
3 1 4
5 2 6
3
4 3 1
5 2 6
4 3 6
5 1 2
3
1 5 6
3 2 4
2 3 5
6 1 4
3
2 5 4
6 1 3
6 3 2
5 4 1
3
3 6 5
2 1 4
3 5 4
2 6 1
3
5 6 3
2 4 1
3 4 6
2 5 1
3
4 5 6
2 3 1
1 2 3
4 6 5
3
3 2 1
6 4 5
3 1 5
2 4 6
3
5 2 3...

output:

4 2 3 1 6 5 
4 2 6 1 5 3 

result:

wrong answer Integer parameter [name=y2] equals to 6, violates the range [1, 3] (test case 1)