QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#824075 | #9834. Keyboard Chaos | 0x3f# | TL | 1ms | 3736kb | C++14 | 1.6kb | 2024-12-21 12:07:29 | 2024-12-21 12:07:29 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int n,c;
string s[N];
vector<pair<int,int>> vec[N];
struct node {
int sz[N],cnt,cost;
bool operator<(node o) const {
return cost>o.cost;
}
};
string sol(int nw) {
int cnt=0;
for(int i=1;i<=n;i++)
if(vec[i][0].first==nw)
cnt++;
priority_queue<node> q;
node top;
for(int i=1;i<=n;i++) top.sz[i]=0;
top.cost=0;
top.cnt=cnt;
q.push(top);
while(!q.empty()) {
node u=q.top();
if(u.cnt==0) {
string ans="";
for(int i=1;i<=n;i++)
for(int j=0;j<u.sz[i];j++)
for(int k=1;k<=vec[i][j].second;k++)
ans+='a'+vec[i][j].first-1;
ans+=nw+'a'-1;
return ans;
}
q.pop();
for(int i=1;i<=n;i++)
if(u.sz[i]+1<(int)vec[i].size()&&vec[i][u.sz[i]].first==nw&&vec[i][u.sz[i]+1].first!=nw) {
node v=u;
v.sz[i]++;
v.cost+=vec[i][u.sz[i]].second;
v.cnt--;
q.push(v);
}
}
return "!!!";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++) {
int cur=-1,cnt=0;
for(int j=0;j<s[i].size();j++)
if(s[i][j]-'a'+1!=cur) {
if(cur!=-1) vec[i].push_back({cur,cnt});
cur=s[i][j]-'a'+1;
cnt=1;
} else cnt++;
if(cur!=-1) vec[i].push_back({cur,cnt});
}
string ans="";
int len=0x3f3f3f3f;
for(int i=1;i<=c;i++) {
string nw=sol(i);
if(len>nw.size()&&nw!="!!!") {
len=nw.size();
ans=nw;
}
}
if(len==0x3f3f3f3f) cout<<"NO\n";
else cout<<ans<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3720kb
input:
1 26 win
output:
a
result:
ok Got unprintable string of length 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 3 abc bca cab
output:
aa
result:
ok Got unprintable string of length 2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
4 2 aab bb a bab
output:
NO
result:
ok ok, can print any string
Test #4:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
7 3 c ba acc bcb ab bac ac
output:
aaaa
result:
ok Got unprintable string of length 4
Test #5:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
7 4 bd cbb ccb a a dda b
output:
ddd
result:
ok Got unprintable string of length 3
Test #6:
score: -100
Time Limit Exceeded
input:
100 7 ag gf gc ad fg gb ge fd ef gc ba cd cc fa fe bg df cd bc cb ff ac ea ag dc da cg fb ef gf ef ca ef cd eg ba cg aa ba bg ea bc ef fg db ag df fb aa bf gd eg af fb ab ea ea cb ag dd dg gg cc af dd ce fg bf de cd bf ba bd gf fb gd cg bc ac ef eg eg db ge eg cf dg bg dd ad ge fg ga ab dg gb ac be ...