QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#824075#9834. Keyboard Chaos0x3f#TL 1ms3736kbC++141.6kb2024-12-21 12:07:292024-12-21 12:07:29

Judging History

This is the latest submission verdict.

  • [2024-12-21 12:07:29]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3736kb
  • [2024-12-21 12:07:29]
  • Submitted

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;
}

詳細信息

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
...

output:


result: