Submission #64757554

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pii pair<int, int>
#define endl '\n'
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

void dbg_out() { cerr << endl; }
template<typename H, typename... T>
void dbg_out(H h, T... t) {
    cerr << ' ' << h;
    dbg_out(t...);
}
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

inline int read() {
    int n=0,f=1,ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        n=n*10+ch-'0';
        ch=getchar();
    }
    return n*f;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,k; cin>>n>>k;
    string s; cin>>s;
    int cnt = 0;
    for(int i = 0;i < n;i++)
    {
        if(s[i] == 'o')
        {
            cnt++;
            if(i && s[i - 1] == '?') s[i - 1] = '.';
            else if(i + 1 < n && s[i + 1] == '?') s[i + 1] = '.';
        }
    }
    cnt = k - cnt; // need cnt o
    if(!cnt)
    {
        for(int i = 0;i < n;i++) 
        {
            if(s[i] == '?') cout<<'.';
            else cout<<s[i];
        }
        return 0;
    }
    int i = 0;
    int cnt2 = 0;
    while(i < n)
    {
        // dbg(i);
        if(s[i] == 'o') i++;
        else if(s[i] == '.') i++;
        else 
        {
            int j = i;
            while(j < n && s[j] == '?') j++;
            int len = j - i;
            if(len&1) cnt2 += (len + 1) / 2;
            else cnt2 += len / 2;
            i = j;
        }
    }
    if(cnt == cnt2)
    {
        int i = 0;
        while(i < n)
        {
            // dbg(i);
            if(s[i] == 'o') i++;
            else if(s[i] == '.') i++;
            else 
            {
                int j = i;
                while(j < n && s[j] == '?') j++;
                int len = j - i;
                if(len&1)
                {
                    for(int k = i;k < j;k++) 
                    {
                        if((k - i + 1)&1) s[k] = 'o';
                        else s[k] = '.';
                    }
                }
                i = j;
            }
        }
        for(int i = 0;i < n;i++) cout<<s[i];
    }
    else
    {
        for(int i = 0;i < n;i++)
        {
            cout<<s[i];
        }
    }
    return 0;
}

Submission Info

Judge Result