QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637405#4273. Good Gamechenxinyang20060 40ms37376kbC++204.1kb2024-10-13 12:39:092024-10-13 12:39:10

Judging History

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

  • [2024-10-13 12:39:10]
  • 评测
  • 测评结果:0
  • 用时:40ms
  • 内存:37376kb
  • [2024-10-13 12:39:09]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#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,m,k;
char s[1000005];
int a[1000005],b[1000005],c[1000005];

vector <pii> answer;
int top;
int stk[1000005];
void psh(int v){
//	printf("psh %d\n",v);
	stk[++top] = v;
}
int pick(){
	assert(top);
	return stk[top--];
}
void clr(int l,int r){
//	printf("clr [%d,%d]\n",l,r);
	assert(r > l);
	if(l % 2 == r % 2){
		answer.eb(l,3);
		r -= 3;
	}
	while(l <= r){
		answer.eb(l,2);
		r -= 2;
	}
}
struct info{
	int _l[2],_r[2];
	info(){
		_l[0] = _l[1] = inf;
		_r[0] = _r[1] = 0;
	}
}dp[1000005];

void fix(info &I,int l,int r){
	if(l > r) return;
	assert(l % 2 == r % 2);
	chkmin(I._l[l % 2],l);
	chkmax(I._r[r % 2],r);
}

int sz;
int d[1000005];
void get(info &I,int up){
	rep(i,I._l[0],min(up,I._r[0])) if(i % 2 == 0) d[++sz] = i;
	rep(i,I._l[1],min(up,I._r[1])) if(i % 2) d[++sz] = i;
}

int chk(info &I,int p){
	return I._l[p % 2] <= p && p <= I._r[p % 2];
}

int valid(int p,int l,int r){
	return (p % 2 == l % 2 && l <= p && p <= r);
}

void dbg(info &I){
	printf("even range [%d,%d] odd range [%d,%d]\n",I._l[0],I._r[0],I._l[1],I._r[1]);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	scanf("%s",s + 1);
	for(int l = 1,r;l <= n;l = r + 1){
		r = l;
		while(r < n && s[r] == s[r + 1]) r++;
		a[++m] = r - l + 1;
	}

	k = 0;
	rep(i,1,m){
		if(a[i] == 1) b[k]++;
		else c[++k] = a[i];
	}
	if(!k){
		printf("-1\n");
		return 0;
	}
	fix(dp[0],b[0],b[0]);
	rep(i,1,k - 1){
		get(dp[i - 1],b[i]);
		while(sz){
			fix(dp[i],b[i] - d[sz],b[i] - d[sz]);
			fix(dp[i],abs(d[sz] - (b[i] + 1)),d[sz] + (b[i] + 1));
			sz--;
		}
		rep(p,0,1){
			int tl = max(b[i] + 1,dp[i - 1]._l[p]),tr = dp[i - 1]._r[p];
			while(tl % 2 != p) tl++;
			if(tl > tr) continue;
			fix(dp[i],tl - (b[i] + 1),tr + (b[i] + 1));
		}
		dbg(dp[i]);
	}
/*	rep(i,1,m) printf("%d ",a[i]);
	printf("\n");
	rep(i,0,k) printf("%d ",b[i]);
	printf("\n");
	rep(i,1,k) printf("%d ",c[i]);
	printf("\n");*/
	if(!chk(dp[k - 1],b[k])){
		printf("-1\n");
		return 0;
	}
	rep(i,1,b[k]) psh(1);
	int x = b[k],y,bb,sum = n - b[k];
	per(i,k - 1,0){
		y = x;x = bb = -1;
		if(i){
			get(dp[i - 1],b[i]);
			while(sz){
				if(b[i] - d[sz] == y) x = d[sz];
				if(valid(y,abs(d[sz] - (b[i] + 1)),d[sz] + (b[i] + 1))) x = d[sz];
				sz--;
			}
//			printf("x=%d\n",x);
			rep(p,0,1){
				int tl = max(b[i] + 1,dp[i - 1]._l[p]),tr = dp[i - 1]._r[p];
				while(tl % 2 != p) tl++;
				if(tl > tr || p + (b[i] + 1) % 2 != y % 2) continue;
				chkmax(tl,y - (b[i] + 1));
				chkmin(tr,y + (b[i] + 1));
				if(tl <= tr) x = tl;
			}		
			assert(x != -1);
			bb = (b[i] + 1 - x + y) / 2;
		}else{
			x = 0;
			bb = b[i];
		}
//		printf("i=%d bi=%d y=%d chose x=%d bb=%d sum=%d\n",i,b[i],y,x,bb,sum);
		assert(x != -1);
		assert(bb <= b[i] + 1);
		sum -= c[i + 1];
		psh(c[i + 1]);
		rep(kk,1,bb){
			clr(sum + 1,sum + pick());
			if(kk != b[i] + 1){
				stk[top]++;
				sum--;
			}else{
				sum -= c[i];
				c[i] += pick();
				sum += c[i];
			}
		}
		rep(kk,1,b[i] - bb){
			psh(1);
			sum--;
		}
	}
	while(top) clr(1,stk[top--]);
	printf("%d\n",SZ(answer));
	for(pii I:answer) printf("%d %d\n",I.first,I.second);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

9
ABAABBBAA

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #51:

score: 0
Wrong Answer
time: 0ms
memory: 30580kb

input:

299
ABABABABABABABABABABABABABABABABABBAABBAABBAABBAAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBAABBBAABBAABBAABBAABBAABBAABBAABBAABBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

even range [32,34] odd range [1061109567,0]
even range [1061109567,0] odd range [31,35]
even range [30,36] odd range [1061109567,0]
even range [1061109567,0] odd range [29,37]
even range [28,38] odd range [1061109567,0]
even range [1061109567,0] odd range [27,39]
even range [26,40] odd range [106110...

result:

wrong output format Expected integer, but "even" found

Subtask #3:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 0ms
memory: 26508kb

input:

5998
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

even range [0,0] odd range [1,3991]
2998
3995 3
3995 2
3995 2
3995 2
3994 2
3993 2
3992 2
3991 2
3990 2
3989 2
3988 2
3987 2
3986 2
3985 2
3984 2
3983 2
3982 2
3981 2
3980 2
3979 2
3978 2
3977 2
3976 2
3975 2
3974 2
3973 2
3972 2
3971 2
3970 2
3969 2
3968 2
3967 2
3966 2
3965 2
3964 2
3963 2
3962 2
...

result:

wrong output format Expected integer, but "even" found

Subtask #4:

score: 0
Wrong Answer

Test #153:

score: 0
Wrong Answer
time: 40ms
memory: 37376kb

input:

999997
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

even range [0,0] odd range [1,666655]
499998
666661 2
666661 2
666661 2
666661 2
666661 2
666660 2
666659 2
666658 2
666657 2
666656 2
666655 2
666654 2
666653 2
666652 2
666651 2
666650 2
666649 2
666648 2
666647 2
666646 2
666645 2
666644 2
666643 2
666642 2
666641 2
666640 2
666639 2
666638 2
666...

result:

wrong output format Expected integer, but "even" found