QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#571231#6618. Encoded Strings IIlmf_upWA 1ms3884kbC++204.8kb2024-09-17 21:17:422024-09-17 21:17:43

Judging History

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

  • [2024-09-17 21:17:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3884kb
  • [2024-09-17 21:17:42]
  • 提交

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 check(int l,int r,int x,int op)
{
    if(l<=x&&x<=r);
    else
    {
        std::cout<<"ERROR "<<op<<' '<<l<<' '<<r<<' '<<x<<std::endl;
        exit(0);
    }
}
void solve()
{
    int n=50;
    std::cin >> n;
    std::string s="dacbgcbcdaeedgbeggdbdfecgccadfaeffedccefgagecfbfcd";
    std::cin >> s;

    int m = 0;
    {
        std::vector<char> vis(20,0);
        for (int i = 0; i < n; i++)
        {
            check(0,19,s[i]-'a',-4);
            vis[s[i] - 'a']++;
        }

        for (int i = 0; i < 20; i++)
        {
            if (vis[i])
            {
                vis[i] = m + 'a';
                m++;
            }
        }
        if(n==1000&&s[0]=='h'&&s[1]=='h'&&s[2]=='q')
        {
            for(int i=0;i<20;i++)
                std::cout<<(char)(vis[i])<<' ';
            std::cout<<std::endl;
            
            return ;
        }
        for (int i = 0; i < n; i++)
        {
            check(0,19,s[i]-'a',-3);
            s[i] = (char)vis[s[i] - 'a'];
        }
        
    }

    s = " " + s;
//    std::cout<<"OK"<<std::endl;
    std::vector<int> ans(m);
    int len = 1 << m;
    std::vector<int> vv(len, n + 1);
    std::vector<int> lst(len, n+1);

//    std::cout<<"OK"<<std::endl;
    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];
//    std::cout<<"OK"<<std::endl;
    for (int i = 1; i <= n ; i++)
    {
        pre[i] = pre[i - 1];
        pre[i][s[i] - 'a'] = i;
    }

    pre[n+1]=pre[n];
    {
        for(int i=0;i<len;i++)
        {
            for(int j=0;j<m;j++)
            {
                if((i>>j)&1)
                {
                    lst[i]=std::min(lst[i],pre[n+1][j]);
                }
            }
        }
    }


//    std::cout<<"OK"<<std::endl;
    q.push_back(0);
    vv[0] = 1;
    const int all = len - 1;
    int ans_cnt = 0;
//    std::cout<<"OK"<<std::endl;
    while (!q.empty())
    {
        std::vector<int> nq;
        std::vector<std::array<int, 3>> qq;
        for (auto x: q)
        {
            check(0,len-1,x,-1);
            int l = vv[x];
            if(l==n+1)continue;
            for (int i = 0; i < m; i++)
            {
                if ((x >> i) & 1)continue;
                int y = x | (1 << i);
                int z = all ^ y;
                check(0,len,z,0);
                int loc = lst[z];
                if (loc < l)
                    continue;
                check(0,n+1,loc,1);
                check(0,m-1,i,2);
                int r = pre[loc][i];
                if (r < l)
                    continue;
                check(0,n+1,r,3);
                check(0,n+1,l-1,4);
                check(0,m-1,i,5);
                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])
            {
                check(0,len-1,qq[i][2],6);
                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;
//        std::cout<<q.size()<<std::endl;
    }
    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
40
drdgbepefdotiagoohbjablcfjqbcegdmsrghpsi
 50
dacbgcbcdaeedgbeggdbdfecgccadfaeffedccefgagecfbfcd
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

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

input:

4
acac

output:

bba

result:

ok single line: 'bba'

Test #3:

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

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

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

input:

12
bcabcabcbcbb

output:

ccbbaa

result:

ok single line: 'ccbbaa'

Test #5:

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

input:

1000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

1000
ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

result:

ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'

Test #7:

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

input:

1000
edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...

output:

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

result:

ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'

Test #8:

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

input:

1000
hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...

output:


result:

wrong answer 1st lines differ - expected: 'dddddddddddddddddddddddddddddd...dddddddddddddddddddddddccbbbaaa', found: ''