Submission #168112

#	Time	Username	Problem	Language	Result	Execution time	Memory
168112		sans	Igra (COCI17_igra)	C++14	100 / 100	5 ms	632 KiB

igra

#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

int a = 0, b = 0, c = 0, N;
vector<char> slavko, ans;
vector<int> segmentA, segmentB, segmentC;

void build(int node, int start, int end, char c, vector<int>& s){
    if(start == end){ s[node] = (slavko[start] == c); return; }
    int mid = (start + end)/2;
    build(2*node+1, start, mid, c, s);
    build(2*node+2, mid+1, end, c, s);
    s[node] = s[2*node+1]+s[2*node+2];
    return;
}

int getTot(int node, int start, int end, int l, int r, vector<int>& s){
    if(start > r or end < l) return 0;
    if(start >= l and end <= r) return s[node];

    int mid = (start+end)/2;
    int p1 = getTot(2*node+1, start, mid, l, r, s);
    int p2 = getTot(2*node+2, mid+1, end, l, r, s);
    return (p1+p2);
}

void solve(int n){
    if(n == N) return;
    int ilerideA = getTot(0, 0, N, n+1, N-1, segmentA);
    int ilerideB = getTot(0, 0, N, n+1, N-1, segmentB);
    int ilerideC = getTot(0, 0, N, n+1, N-1, segmentC);

    if(a and slavko[n] != 'a' and a-1 + c >= ilerideB and a-1 + b >= ilerideC){
        ans[n] = 'a';
        a--;
    }
    else if(b and slavko[n] != 'b' and b-1 + c >= ilerideA and b-1 + a >= ilerideC){
        ans[n] = 'b';
        b--;
    }
    else if(c and slavko[n] != 'c' and c-1 + a >= ilerideB and c-1 + b >= ilerideA){
        ans[n] = 'c';
        c--;
    }
    solve(n+1);
}

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    string str; cin >> str;

    for(int i = 0; i < N; ++i){
        if(str[i] == 'a') a++;
        else if(str[i] == 'b') b++;
        else if(str[i] == 'c') c++;
    }

    ans.resize(N);
    segmentA.resize(4*N);
    segmentB.resize(4*N);
    segmentC.resize(4*N);
    slavko.resize(N); for(int i = 0; i < N; ++i) cin >> slavko[i];
    build(0, 0, N, 'a', segmentA);
    build(0, 0, N, 'b', segmentB);
    build(0, 0, N, 'c', segmentC);
    solve(0);

    for(int i = 0; i < N; ++i) cout << ans[i];
    cout << endl;

    return 0;
}

//cikisir

• Subtask 1: 100 / 100