# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
408593 | LptN21 | Igra (COCI17_igra) | C++14 | 1 ms | 312 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define oo 1e9
#define eps 1e-9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
const int N = 5000+7, M=13+7;
const int MOD = 1e9+7;
int n, m, k, t;
char x[N], y[N];
int sl[3], slc[3];
int slt[3], slct[3];
void renew() {
for(int i=0;i<3;i++)
slt[i]=sl[i], slct[i]=slc[i];
}
bool check(int i, int j) {
if(y[i]==j+'a') return 0;
for(int i=0, lim=min(sl[0], slc[1]);i<=lim;i++) {
renew();
slt[0]-=i, slct[1]-=i;
if(slt[2]<slct[1]||slt[0]>slct[2]) continue;
if(slt[0]+slt[1]<slct[2]) continue;
return 1;
}
return 0;
}
void solve(int idx) {
if(idx==n) return;
slc[y[idx]-'a']--;
for(int j=0;j<3;j++) {
sl[j]--;
if(check(idx, j)) {
printf("%c", j+'a');
solve(idx+1);
break;
}
sl[j]++;
}
}
signed main() {
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//fastIO;
scanf("%d", &n);
scanf("%s%s", &x, &y);
for(int i=0;i<n;i++) sl[x[i]-'a']++, slc[y[i]-'a']++;
solve(0);
return 0;
}
/* stuff you should look for
- int overflow, array bounds
- special cases (n=1?)
- do smth instead of do nothing and stay organized
- WRITE STUFF DOWN
- DONT JUST STICK ON ONE APPROACH
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |