Submission #26958490

---

Source Code Expand

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_fuction
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<int,int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
    #define BUF_SIZE (1<<21)
    #define OUT_SIZE (1<<21)
    bool IOerror=0;
    inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;}
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
    inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
    inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
        inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(int x){print(x);out('\n');}
        inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(ll x){print(x);out('\n');}
        inline void print(double x,int y){//y<18
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
        }
        inline void println(double x,int y){print(x,y);out('\n');}
        inline void print(char *s){while(*s)out(*s++);}
        inline void println(char *s){while(*s)out(*s++);out('\n');}
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef OUT_SIZE
    #undef BUF_SIZE
}using namespace IO;
inline int abs(int x){return x<0?-x:x;}
inline ll abs(ll x){return x<0?-x:x;}
inline double abs(double x){return x<0?-x:x;}
inline int max(const int &a,const int &b){return a>b?a:b;}
inline ll max(const ll &a,const ll &b){return a>b?a:b;}
inline double max(const double &a,const double &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a<b?a:b;}
inline ll min(const ll &a,const ll &b){return a<b?a:b;}
inline double min(const double &a,const double &b){return a<b?a:b;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline void swap(ll &x,ll &y){x^=y^=x^=y;}
inline void swap(double &x,double &y){double t=x;x=y,y=t;}
inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
struct Stack{
	#define N (1000013)
	int s[N],t;
	inline void clear(){t=0;}
	Stack(){clear();}
	inline void push(int x){s[++t]=x;}
	inline void pop(){--t;}
	inline int top(){return s[t];}
	inline bool empty(){return !t;}
	#undef N
};
struct Queue{
	#define N (1000013)
	int q[N],h,t;
	inline void clear(){q[h=t=1]=0;}
	Queue(){clear();}
	inline void push(int x){q[madd(t,1,N)]=x;}
	inline void push_front(int x){q[mdel(h,1,N)]=x;}
	inline void pop(){madd(h,1,N);}
	inline void pop_back(){mdel(t,1,N);}
	inline int front(){return q[h];}
	inline int back(){return q[t];}
	inline int ffront(){return q[madd(h,1,N)];}
	inline int bback(){return q[mdel(t,1,N)];}
	inline bool empty(){return madd(t,1,N)==h;}
	#undef N
};
template<class T>struct RP_Heap{
	#define MAXN 100013
	#define MAXM 1000013
	#define Log_Phi_N 29
    struct ListNode;
    struct Node{T val;int rank;Node *l,*r,*fa;ListNode *p;Node(){}Node(T _val,int _rank=0,Node* _l=0,Node* _r=0,Node* _fa=0):val(_val),rank(_rank),l(_l),r(_r),fa(_fa){}}t[MAXN+2],*p[MAXN+2],*min,*bucket[Log_Phi_N+1];
    int cnt,siz;bool has_min;
    struct ListNode{Node *ptr;ListNode *pre,*nxt;};
    struct List{
        ListNode* head;
		List(){head=new ListNode();head->ptr=NULL;head->nxt=head;head->pre=head;}
        inline void insert(Node* _ptr){ListNode* u=new ListNode();u->ptr=_ptr;u->pre=head;u->nxt=head->nxt;head->nxt->pre=u;head->nxt=u;_ptr->p=u;}
        inline void remove(ListNode* u){u->pre->nxt=u->nxt;u->nxt->pre=u->pre;u->ptr->p=NULL;delete u;}
    }list;
    RP_Heap(){for(int i=0;i<MAXN;i++) p[i]=&t[i];has_min=0;memset(bucket,0,sizeof(bucket));}
    inline Node* new_Node(T v){return (&(*p[cnt++]=Node(v,0,NULL,NULL,NULL)));}
    inline void swap(Node* &x,Node* &y){ Node* temp=x;x=y;y=temp; }
    inline Node* link(Node* u,Node* v){if(v->val<u->val) swap(u,v);v->r=u->l;if(v->r)v->r->fa=v;u->l=v;v->fa=u;u->rank++;return u;}
    inline Node* update_min(Node* u){if(!has_min||u->val<min->val)min=u,has_min=1;return u;}
    inline Node* push(T _val){Node* u=new_Node(_val);list.insert(update_min(u));siz++;return u;}
    inline T top(){return min->val;}
    inline int size(){return siz;}
    inline bool empty(){return siz==0;}
    inline void pop(){
        siz--;list.remove(min->p);has_min=0;int rk;Node *next_node,*u;ListNode *first=list.head->nxt;
        for(u=min->l;u;u=next_node) next_node=u->r,u->fa=u->r=NULL,rk=u->rank,bucket[rk]?(list.insert(update_min(link(u,bucket[rk]))),bucket[rk]=NULL):bucket[rk]=u;
        for(ListNode *i=first,*next_node;i!=list.head;i=next_node) u=i->ptr,rk=u->rank,next_node=i->nxt,list.remove(i),bucket[rk]?(list.insert(update_min(link(u,bucket[rk]))),bucket[rk]=NULL):bucket[rk]=u;
        for(int i=0;i<=Log_Phi_N;i++)if(bucket[i])list.insert(update_min(bucket[i])),bucket[i]=NULL;
    }
    inline void modify(Node* u,T key){
    	u->val=key;if(u->fa==NULL) return update_min(u);
        if(u->l) u->rank=u->l->rank+1;else u->rank=0;if(u->r) u->r->fa=u->fa;if(u==u->fa->l) u->fa->l=u->r;else u->fa->r=u->r;
        int temp,lrk,rrk;
        for(Node* v=u->fa;v;v=v->fa){
            lrk=v->l?v->l->rank:-1,rrk=v->r?v->r->rank:-1,temp=max(lrk,rrk)+(abs(lrk-rrk)<=1?1:0);
            if(temp==v->rank)break;
            v->rank=temp;
        }
        u->fa=u->r=NULL,list.insert(update_min(u));
    }
    #undef MAXN
	#undef MAXM
	#undef Log_Phi_N
};
namespace ST{
	const int N=1e5+13,logN=21;
	int f[N][logN];
	inline void init(int n){
		int k=log(n)/log(2)+1;
		for(int j=1;j<=k;j++)
			for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
	inline int query(int L,int R){int k=log(R-L+1)/log(2);return max(f[L][k],f[R-(1<<k)+1][k]);}
}
namespace Union{
	const int N=1e5+13;
	int fa[N];
	inline void init(int n){for(int i=1;i<=n;++i) fa[i]=i;}
	inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	inline void merge(int u,int v){int x=find(u),y=find(v);if(x!=y)fa[x]=y;}
	inline bool query(int u,int v){return find(u)==find(v);}
}
namespace Gauss{
	const int N=100+13;
	const double eps=1e-6;
	double a[N][N];
	inline bool Gauss(double *ans,int n){
		for(int i=1;i<=n;++i){
			int r=i;
			for(int j=i+1;j<=n;++j)
				if(fabs(a[r][i])>=fabs(a[j][i])) r=j;
			if(fabs(a[r][i])<eps) return 0;
			if(i!=r) std::swap(a[i],a[r]);
			double div=a[i][i];
			for(int j=i;j<=n+1;++j) a[i][j]/=div;
			for(int j=i+1;j<=n;++j){
				div=a[j][i];
				for(int k=i;k<=n+1;++k) a[j][k]-=a[i][k]*div;
			}
		}
		ans[n]=a[n][n+1];
		for(int i=n-1;i>=1;--i){
			ans[i]=a[i][n+1];
			for(int j=i+1;j<=n;++j) ans[i]-=a[i][j]*ans[j];
		}
		return 1;
	}
}
namespace qwaszx{
	const int N=5e6;
	ll big_phi[N],big_mju[N],phi[N+4],mju[N+4];int prime[N];bool vis[N+4];int cnt,t;
	inline ll sum_id(ll n){return n*(n+1)/2;}
	inline ll sum_1(int n){return n;}
	inline ll sum_e(int n){return 1;}
	inline void init(){
		phi[1]=1,mju[1]=1;
		for(int i=2;i<=N;++i){
			if(!vis[i]) prime[++cnt]=i,mju[i]=-1,phi[i]=i-1;
			for(int j=1;j<=cnt&&i*prime[j]<=N;++j){
				vis[i*prime[j]]=1;
				if(i%prime[j]==0){mju[i*prime[j]]=0,phi[i*prime[j]]=phi[i]*prime[j];break;}
				mju[i*prime[j]]=mju[i]*-1,phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
		for(int i=1;i<=N;++i) mju[i]+=mju[i-1],phi[i]+=phi[i-1];
	}
	ll sum_phi(int n){
		if(n<=N) return phi[n];
		if(big_phi[t/n]) return big_phi[t/n];
		ll c=sum_id(n);
		for(ll l=2,r;l<=n;l=r+1) r=n/(n/l),c-=(sum_1(r)-sum_1(l-1))*sum_phi(n/l);
		return big_phi[t/n]=c;
	}
	ll sum_mju(int n){
		if(n<=N) return mju[n];
		if(big_mju[t/n]) return big_mju[t/n];
		ll c=sum_e(n);
		for(ll l=2,r;l<=n;l=r+1) r=n/(n/l),c-=(sum_1(r)-sum_1(l-1))*sum_mju(n/l);
		return big_mju[t/n]=c;
	}
}
const int mod=998244353;
namespace Useful_little_fuction{
	inline void Oninv(int *inv,int n,int p){inv[1]=1;for(int i=2;i<=n;++i) inv[i]=(ll)(p-p/i)*inv[p%i]%p;}
	const int NN=100+13;
	struct Matrix{
		int h,w,d[NN][NN];
		Matrix(){memset(d,0,sizeof d);}
		Matrix operator *(const Matrix &A)const{
			Matrix C;C.h=h,C.w=A.w;
			for(int i=1;i<=h;++i)
				for(int j=1;j<=A.w;++j)
					for(int k=1;k<=w;++k)
						C.d[i][j]=(C.d[i][j]+(ll)d[i][k]*A.d[k][j]%mod)%mod;
			return C;
		}
	};
	inline Matrix qpow(Matrix A,int k){Matrix S=A;--k;for(;k;k>>=1,A=A*A)if(k&1)S=S*A;return S;}
	inline int qpow(int a,int k,int p=0){if(!p)p=::mod;int s=1;for(;k;k>>=1,a=(ll)a*a%p)if(k&1)s=(ll)s*a%p;return s;}
	inline int invv(int a,int p=0){if(!p)p=::mod;return qpow(a,p-2,p);}
	inline ll mmul(ll a,ll k,ll p){ll s=0;for(;k;k>>=1,a=(a+a)%p)if(k&1)s=(s+a)%p;return s;}
	const int MM=63;
	struct Onbase{
		int p[MM];
		inline void insert(ll x){for(int i=MM-1;i>=0;--i){if((x>>i)&1){if(!p[i]){p[i]=x;break;}x^=p[i];if(!x) return;}}}
		inline ll query(){ll res=0;for(int i=MM-1;i>=0;--i)if((res^p[i])>res) res^=p[i];return res;}
	};
}using namespace ulf;
namespace Math{
	const int N=2e7+13;
	bool b[N];
	inline void Onshai(int *prm,int &pcnt,int n){
		for(int i=2;i<=n;++i){
			if(!b[i]) prm[++pcnt]=i;
			for(int j=1;j<=pcnt&&i*prm[j]<=n;++j){
				b[i*prm[j]]=1;
				if(i%prm[j]==0) break;
			}
		}
	}
	void exgcd(int a,int b,int &x,int &y){if(!b) return x=1,y=0,void();exgcd(b,a%b,y,x);y-=(a/b)*x;}
	void exgcd(ll a,ll b,ll &x,ll &y){if(!b) return x=1,y=0,void();exgcd(b,a%b,y,x);y-=(a/b)*x;}
	inline ll crt(ll *a,ll *b,int n){
		ll sum=1,res=0;
		for(int i=1;i<=n;++i) sum*=a[i];
		for(int i=1;i<=n;++i){
			ll x,y,tmp=sum/a[i];
			ll g=gcd(tmp,(ll)a[i]);exgcd(tmp,a[i],x,y);
			x=(x%a[i]+a[i])%a[i];
			res+=b[i]*tmp*x;
		}
		return res;
	}
	inline int phi(int x){
		int ans=x,n=sqrt(x);
		for(int i=2;i<=n;++i)
			if(x%i==0){ans=ans/i*(i-1);while(x%i==0) x/=i;}
		if(x>1) ans=ans/x*(x-1);
		return ans;
	}
	inline ll excrt(ll *a,ll *b,int n){
		for(int i=2;i<=n;++i){
			ll g=gcd(a[i-1],a[i]),x,y;
			exgcd(a[i-1]/g,a[i]/g,x,y);
			a[i]*=a[i-1]/g;
			b[i]=(mmul(mmul((b[i]-b[i-1])/g,(x%a[i]+a[i])%a[i],a[i]),a[i-1],a[i])+b[i-1])%a[i];
			b[i]=(b[i]+a[i])%a[i];
		}
		return b[n];
	}
	inline int BSGS(int a,int b,int p){
		std::unordered_map<int,int> ha;ha.clear();
		int t=sqrt(p)+1;int tmp=1;
		for(int i=0;i<t;++i) ha[(ll)b*tmp%p]=i+1,tmp=(ll)tmp*a%p;
		a=tmp;
		for(int i=1;i<=t;++i){
			tmp=qpow(a,i,p);
			if(ha[tmp]) return i*t-ha[tmp]+1;
		}
		return -1;
	}
}
const int N=6e5+13;
char s[N];
int n,ans[N];
std::queue<int> p[4][4];
int main(){
//file();
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	read(n),read(s+1);
	for(int i=1;i<=n;++i){
		p[1][s[i]-'A'+1].push(i);
		p[2][s[i+n]-'A'+1].push(i+n);
		p[3][s[i+n+n]-'A'+1].push(i+n+n);
	}
	int cnt=1;
	while(cnt<=6){
		int nowx=1,nowy=1;
		for(int i=1;i<=3;++i)
			for(int j=1;j<=3;++j)
				if(!p[i][j].empty()){
					if(p[nowx][nowy].empty()) nowx=i,nowy=j;
					else if(p[i][j].size()<p[nowx][nowy].size()) nowx=i,nowy=j;
				}
		if(p[nowx][nowy].empty()) break;
		int ccnt=p[nowx][nowy].size(),see=0,tmp=0;
		for(int i=1;i<=3;++i){
			if(i==nowx) continue;
			bool ok=0;
			if(!see) see=i;
			for(int j=1;j<=3;++j){
				if(j==nowy||j==tmp||p[i][j].empty()) continue;
				if(!tmp) tmp=j;ok=1;
				break;
			}
			if(!ok) see=i;
		}
		for(int i=1;i<=3;++i){
			if(i==nowx){
				int j=nowy;
				while(!p[i][j].empty()) ans[p[i][j].front()]=cnt,p[i][j].pop();
				continue;
			}
			if(i==see){
				int j=tmp,o=ccnt;
				while(o--) ans[p[i][j].front()]=cnt,p[i][j].pop();
				continue;
			}
			for(int j=1;j<=3;++j){
				if(j==nowy||j==tmp) continue;
				int o=ccnt;
				while(o--) ans[p[i][j].front()]=cnt,p[i][j].pop();
				break;
			}
		}
		++cnt;
	}
	for(int i=1;i<=3*n;++i) print(ans[i]);
	return 0;
}

Submission Info

Compile Error

./Main.cpp:40:82: warning: for loop has empty body [-Wempty-body]
    inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
                                                                                 ^
./Main.cpp:40:82: note: put the semicolon on a separate line to silence this warning
./Main.cpp:41:81: warning: for loop has empty body [-Wempty-body]
    inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
                                                                                ^
./Main.cpp:41:81: note: put the semicolon on a separate line to silence this warning
./Main.cpp:42:85: warning: for loop has empty body [-Wempty-body]
    inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
                                                                                    ^
./Main.cpp:42:85: note: put the semicolon on a separate line to silence this warning
./Main.cpp:43:67: warning: for loop has empty body [-Wempty-body]
    inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
                                                                  ^
./Main.cpp:43:67: note: put the semicolon on a separate line to silence this warning
./Main.cpp:44:58: warning: for loop has empty body [-Wempty-body]
    inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
                                                         ^
./Main.cpp:44:58: note: put the semicolon on a separate line to silence this warning
./Main.cpp:55:201: warning: for loop has empty bo...

Judge Result