QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#753314#6617. Encoded Strings Issx#WA 0ms3856kbC++201.6kb2024-11-16 12:20:082024-11-16 12:20:10

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 12:20:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-11-16 12:20:08]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 7;
const int N = 3e5 + 50;

ll n, st[N];
char s[N];
vector<ll> e[50];

ll get(ll l, ll r)
{
    ll res = 0;
    for (int i = l; i <= r; i++) st[s[i]] = 0;
    for (int i = l; i <= r; i++)
    {
        if (st[s[i]] == 0)
        {
            st[s[i]] = 1;
            res ++;
        }
    }
    return res;
}

void solve()
{
    ll l, r;
    cin >> n;
    string ans;
    char c;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        e[s[i] - 'a' + 1].push_back(i);
    }
    for (int i = 1; i <= 30; i++) e[i].push_back(n + 1);
    r = n;
    int tx, tl, tr, p, mx;
    for (int i = 1; i <= r; i++)
    {
        tx = s[i] - 'a' + 1;
        p = 0, mx = 0;
        for (int j = 0; j < e[tx].size() - 1; j++)
        {
            tl = e[tx][j] + 1, tr = e[tx][j + 1] - 1;
            if (tl > r) break;
            if (tr > r) tr = r;
            if (mx == 0) p = r;
            if (tl > tr) continue;
            //cout << get(tl, tr) << '\n';
            if (get(tl, tr) >= mx)
            {
                mx = get(tl, tr);
                p = e[tx][j + 1] - 1;
            }
            
        }
        //cout << mx << '\n';
        c = mx + 'a';
        r = min((int)r, (int)p);
        ans += c;
        //cout << r << '\n';
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll T = 1;
    //cin >> T;
    while (T --)
    {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

3
aca

output:

ba

result:

ok single line: 'ba'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3556kb

input:

12
bcabcabcbcbb

output:

ccbc

result:

wrong answer 1st lines differ - expected: 'cbacba', found: 'ccbc'