QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#35334#962. Thanks to MikeMirzayanovFroggyguaWA 2ms3692kbC++171.5kb2022-06-15 10:52:062022-06-15 10:52:07

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-15 10:52:07]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3692kb
  • [2022-06-15 10:52:06]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define N 20020
typedef long long ll;
int n,a[N];
vector<vector<int> > ans;
void work(vector<int> V){
	ans.push_back(V);
	int l=1,r=0;
	for(auto x:V){
		r=l+x;
		reverse(a+l,a+r);
		l=r;
	}
	assert(r==n+1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int d=14;d>=0;--d){
		while(true){
			vector<int> A;
			vector<pair<int,int> > tmp;
			int len=1;
			bool need=0;
			for(int i=1;i<=n;++i){
				if(i<n&&(a[i]>>d)==(a[i+1]>>d)){
					++len;
					continue;
				}
				tmp.emplace_back(a[i]>>d&1,len);
				if(i==n||(a[i]>>d+1)!=(a[i+1]>>d+1)){
					if(tmp[0].first==1){
						tmp.insert(tmp.begin(),make_pair(0,0));
					}
					if(tmp.size()>2)need=1;
					for(int i=0;i<(int)tmp.size();i+=3){
						if(tmp[i].second>0){
							A.push_back(tmp[i].second);
						}
						if(i+1<(int)tmp.size()){
							A.push_back(tmp[i+1].second+(i+2>=(int)tmp.size()?0:tmp[i+2].second));
						}
					}
					tmp.clear();
				}
				len=1;
			}
			if(!need)break;
			work(A);
			break;
		}
	}
	if(ans.size()&1){
		ans.push_back(vector<int>(n,1));
	}
	int cnt=0;
	for(int i=0;i<(int)ans.size();++i){
		if(ans[i].size()==1)continue;
		++cnt;
	}
	cout<<cnt<<'\n';
	int op=0;
	for(int i=0;i<(int)ans.size();++i){
		if(ans[i].size()==1)continue;
		auto A=ans[i];
		if(op)reverse(A.begin(),A.end());
		op^=1;
		cout<<A.size()<<' ';
		for(auto x:A)cout<<x<<' ';
		cout<<'\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3532kb

input:

4
3 1 2 4

output:

2
3 2 1 1 
3 1 2 1 

result:

ok OK

Test #2:

score: 0
Accepted
time: 2ms
memory: 3496kb

input:

6
6 5 4 3 2 1

output:

1
6 1 1 1 1 1 1 

result:

ok OK

Test #3:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

1
1

output:

0

result:

ok OK

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 3692kb

input:

10
3 8 7 4 6 2 9 10 1 5

output:

4
4 1 5 2 2 
4 2 3 3 2 
7 2 2 1 1 2 1 1 
7 1 1 1 2 2 1 2 

result:

wrong answer the permutation is not sorted