Submission #634406

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634406	2022-08-24T11:05:00 Z	inksamurai	Igra (COCI17_igra)	C++17	100 / 100	1 ms	384 KB

igra

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3PGDklf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

signed main(){
_3PGDklf;
	int n;
	cin>>n;
	auto stovi=[&](string s)->vi{
		vi tmp;
		for(auto c:s){
			tmp.pb(c-'a');
		}
		return tmp;
	};
	string s;
	cin>>s;
	vi a=stovi(s);
	cin>>s;
	vi b=stovi(s);
	const int m=3;
	vi cnta(m),cntb(m);
	rep(i,n){
		cnta[a[i]]+=1;
		cntb[b[i]]+=1;
	}
	vi usd(n);
	string pns="";
	rep(i,n){
		int ch=b[i];
		cntb[ch]-=1;
		rep(j,m){
			if(ch==j or !cnta[j]) continue;
			cnta[j]-=1;
			bool gok=0;
			rep(x,cnta[0]+1){
				bool pok=1;
				vi nowa=cnta,nowb=cntb;
				if(nowb[1]>=x){
					// a->b
					nowa[0]-=x;
					nowb[1]-=x;
					// a->c
					nowb[2]-=nowa[0];
					nowa[0]=0;
					if(nowb[1]<0 or nowb[2]<0) pok=0;
					// c->b
					nowa[2]-=nowb[1];
					nowb[1]=0;
					// b->c
					nowa[1]-=nowb[2];
					nowb[2]=0;
					if(nowa[1]<0 or nowa[2]<0) pok=0;
					// b->a and c->a
					nowb[0]-=(nowa[1]+nowa[2]);
					nowa[1]=0;
					nowa[2]=0;
					rep(v,m){
						if(nowa[v]!=0 or nowb[v]!=0){
							pok=0;
						}
					}
				}
				if(pok){
					gok=1;
					break;
				}
			}
			if(gok){
				usd[i]=1;
				pns+=(char)('a'+j);
				break;
			}
			cnta[j]+=1;
		}
	}
	assert(usd==vi(n,1));
	print(pns);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct