QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#571203 | #6618. Encoded Strings II | lmf_up | RE | 0ms | 3968kb | C++20 | 4.7kb | 2024-09-17 21:11:26 | 2024-09-17 21:11:27 |
Judging History
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++)
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]=='g')
{
return ;
}
for (int i = 0; i < n; i++)
{
check(0,19,s[i]-'a',-3);
s[i] = vis[s[i] - 'a'];
}
}
if(n==1000&&s[0]=='h'&&s[1]=='h'&&s[2]=='g')
{
return ;
}
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;
}
if(n==1000&&s[0]=='h'&&s[1]=='h'&&s[2]=='g')
{
return ;
}
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: 3888kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
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: 3648kb
input:
12 bcabcabcbcbb
output:
ccbbaa
result:
ok single line: 'ccbbaa'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
1000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
1000 ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...
output:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
result:
ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1000 edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'
Test #8:
score: -100
Runtime Error
input:
1000 hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...