QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368620#962. Thanks to MikeMirzayanovchenxinyang2006WA 24ms238388kbC++143.8kb2024-03-27 14:23:402024-03-27 14:23:41

Judging History

This is the latest submission verdict.

  • [2024-03-27 14:23:41]
  • Judged
  • Verdict: WA
  • Time: 24ms
  • Memory: 238388kb
  • [2024-03-27 14:23:40]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n;
int a[20005],b[20005],tmp[20005];

int k;
int c[20005];
void oper(int m,vector <int> &I){
	int N = m,pos = 0;
	for(int s:I){
		rep(_k,N - s + 1,N) tmp[++pos] = b[_k];
		N -= s;
	}
	rep(_k,1,m) b[_k] = tmp[_k];
	reverse(I.begin(),I.end());
}

void ooper(int m,vector <int> &I){
	reverse(I.begin(),I.end());
//	rep(i,1,m) printf("%d ",b[i]);
//	printf("\n");
//	printf("ooper\n");
	oper(m,I);
//	rep(i,1,m) printf("%d ",b[i]);
//	printf("\n");
}

vector <int> ret[125];
int solve01(int m){
	int sz = 0;
	while(1){
		k = 0;
		for(int l = 1,r;l <= m;l = r + 1){
			r = l;
			while(r < m && b[r + 1] == b[r]) r++;
			c[++k] = r - l + 1;
		}
		
		if(k == 1) return sz;

		if(k == 2){
			if(!b[1]) return sz;
	
			sz++;
//			ret[sz].clear();	
			ret[sz].eb(c[1]);
			ret[sz].eb(c[2]);
			return sz;
		}

		sz++;
//		ret[sz].clear();
		int op = 0;
		while(k){
			if(k == 1){
				ret[sz].eb(c[k]);
				break;
			}

			if(!op){
				if(k >= 2) ret[sz].eb(c[k] + c[k - 1]);
				k -= 2;
			}else{
				ret[sz].eb(c[k]);
				k--;
			}
			op ^= 1;
		}
		oper(m,ret[sz]);
	}
}

int ssolve01(int m){
/*	printf("ssolve01 length=%d\n",m);
	rep(i,1,m) printf("%d",b[i]);
	printf("\n");*/
	int sz = solve01(m);
/*	rep(i,1,sz){
		for(int s:ret[i]) printf("%d ",s);
		printf("\n");
	}*/
	return sz;
}

vector <int> res[80005][125];
#define ls (rt * 2)
#define rs (rt * 2 + 1)
int solve(int rt,int l,int r){
//	printf("solve %d [%d,%d]\n",rt,l,r);
	if(l == r) return 0;
	int mid = (l + r) >> 1;
	rep(i,0,r - l) b[i + 1] = (a[l + i] > mid);
	int sz = ssolve01(r - l + 1);
/*	rep(i,1,sz){
		for(int s:ret[i]) printf("%d ",s);
		printf("\n");
	}*/
	rep(i,0,r - l) b[i + 1] = a[l + i];
	rep(i,1,sz) ooper(r - l + 1,ret[i]);
	rep(i,0,r - l) a[l + i] = b[i + 1];
//	printf("[%d,%d]\n",l,r);

//	rep(i,l,r) printf("%d ",a[i]);
//	printf("\n");
	rep(i,1,sz) swap(res[rt][i],ret[i]);
	int pl = solve(ls,l,mid),pr = solve(rs,mid+1,r);

	rep(_k,pl + 1,pr) res[ls][_k].eb(mid - l + 1);
	rep(_k,pr + 1,pl) res[rs][_k].eb(r - mid);

	
	rep(_k,1,max(pl,pr)){
		if(_k & 1){
			for(int s:res[ls][_k]) res[rt][sz + _k].eb(s);
			for(int s:res[rs][_k]) res[rt][sz + _k].eb(s);
		}else{
			for(int s:res[rs][_k]) res[rt][sz + _k].eb(s);
			for(int s:res[ls][_k]) res[rt][sz + _k].eb(s);			
		}
	}
/*	printf("[%d,%d] len=%d\n",l,r,sz + max(pl,pr));
	rep(_k,1,sz + max(pl,pr)){
		for(int s:res[rt][_k]) printf("%d ",s);
		printf("\n");
	}*/
	if(max(pl,pr) % 2 == 0) return max(pl,pr) + sz;

	res[rt][sz + max(pl,pr) + 1].eb(r - mid);
	res[rt][sz + max(pl,pr) + 1].eb(mid - l + 1);
	return max(pl,pr) + sz + 1;
}
mt19937 rnd(0);

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
/*	rep(i,1,n){
		a[i] = i;
		swap(a[i],a[rnd() % i + 1]);
	}*/
	int q = solve(1,1,n);
	printf("%d\n",q);
	rep(i,1,q){
		for(int s:res[1][i]) printf("%d ",s);
		printf("\n");
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 24ms
memory: 238388kb

input:

4
3 1 2 4

output:

3
1 3 
2 1 1 
2 2 

result:

wrong answer Integer 1 violates the range [2, 4]