QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#569738#6618. Encoded Strings IIlmf_upWA 0ms3808kbC++203.7kb2024-09-17 09:56:292024-09-17 09:56:30

Judging History

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

  • [2024-09-17 09:56:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3808kb
  • [2024-09-17 09:56:29]
  • 提交

answer

#include<bits/stdc++.h>

#define lmf_up signed main()
#define lmf_up_up std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
const int TIAO = 1;
//const int mod = 998244353;
const int maxn = 3e5 + 10;

//#define int long long
inline void read(int &x)
{
    x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
}

const int INF = 1e9;

void solve()
{
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    int m = 0;
    {
        std::vector<char> vis(20);
        for (int i = 0; i < n; i++)
            vis[s[i] - 'a']++;
        for (int i = 0; i < 20; i++)
        {
            if (vis[i])
            {
                vis[i] = m + 'a';
                m++;
            }
        }
        for (int i = 0; i < n; i++)
            s[i] = vis[s[i] - 'a'];
    }
    s = " " + s;
    std::vector<int> ans(m);
    int len = 1 << m;
    std::vector<int> vv(len, n + 1);
    std::vector<int> lst(len, 0);
    {
        int res = 0;
        for (int i = n; i >= 1; i--)
        {
            int v = s[i] - 'a';
            res |= 1 << v;
            lst[res] = std::max(lst[res], i);
        }
        for (int i = 0; i < len; i++)
        {
            for (int j = (i - 1) & i; j; j = (j - 1) & i)
            {
                lst[j] = std::max(lst[j], lst[i]);
            }
        }
        lst[0] = n + 1;
    }
    std::vector<int> q;
    std::vector<std::vector<int>> sum(n + 2, std::vector<int>(m));
    std::vector<std::vector<int>> pre(n + 2, std::vector<int>(m));
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1];
        sum[i][s[i] - 'a']++;
    }
    sum[n+1]=sum[n];
    for (int i = 1; i <= n ; i++)
    {
        pre[i] = pre[i - 1];
        pre[i][s[i] - 'a'] = i;
    }
    pre[n+1]=pre[n];
    q.push_back(0);
    vv[0] = 1;
    const int all = len - 1;
    int ans_cnt = 0;
    while (!q.empty())
    {
        std::vector<int> nq;
        std::vector<std::array<int, 3>> qq;
        for (auto x: q)
        {
            int l = vv[x];
            if(l==n)continue;
            for (int i = 0; i < m; i++)
            {
                if ((x >> i) & 1)continue;
                int y = x | (1 << i);
                int z = all ^ y;
                int loc = lst[z];
                if (loc < l)
                    continue;
                int r = pre[loc][i];
                if (r < l)
                    continue;
                qq.push_back({sum[r][i] -  sum[l - 1][i] , r + 1, y});

            }
        }
        if(qq.empty())break;
        std::sort(qq.begin(), qq.end(), std::greater());
        for (int i = 0; i < qq.size(); i++)
        {
            if (qq[i][0] == qq[0][0])
            {
                vv[qq[i][2]] = std::min(vv[qq[i][2]], qq[i][1]);
                nq.push_back(qq[i][2]);
            }
            else break;
        }
        ans[ans_cnt] = qq[0][0];
        ans_cnt++;
        if (ans_cnt == m)break;
        if(nq.empty())break;
        std::sort(nq.begin(), nq.end());
        nq.erase(std::unique(nq.begin(), nq.end()), nq.end());
        q = nq;
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < ans[i]; j++)
            std::cout << (char) ('a' +m- i-1);
    }


}

lmf_up
{
    lmf_up_up
//    if(TIAO)
//        freopen("P4180_12.in","r",stdin);
//    std::cout << std::fixed << std::setprecision(4);
    int T = 1;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }
}
/*
37
brjnepdaqisnqfipjdodrbetlcslhaeilhnad
41
qdkeehrsjaarcecnimitcbtqpohgcnbonhhlaslpq

 */

詳細信息

Test #1:

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

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

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

input:

4
acac

output:

bb

result:

wrong answer 1st lines differ - expected: 'bba', found: 'bb'