QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#823982#9834. Keyboard Chaos0x3f#WA 1ms3624kbC++141.4kb2024-12-21 11:24:292024-12-21 11:24:30

Judging History

This is the latest submission verdict.

  • [2024-12-21 11:24:30]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3624kb
  • [2024-12-21 11:24:29]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=1010;
int n,c,lim;
string s[N];
bool g[26][26];
struct node {
	string nw;int step;
	bool operator < (const node &o) const {
		return step>o.step;
	}
};
map<node,bool> mp;

string bfs(int c) {
	bool flg=false;
	for(int i=1;i<=n;i++)
		if(c==s[i][0]-'a'+1) {
			flg=true;
			break;
		}
	if(flg==false) {
		string ans="";
		ans+=c+'a'-1;
		return ans;
	} 
	priority_queue<node> q;
	string nw;
	nw+=c+'a'-1;
	q.push({nw,1});
	while(!q.empty()) {
		node u=q.top();
		q.pop();
		if(mp.count(u)) continue;
		mp[u]=true;
		if(u.nw.size()>lim) continue;
		int back=u.nw[u.nw.size()-1]-'a'+1;
		for(int i=1;i<=c;i++)
			if(g[back][i]==false) {
				string ans=u.nw;
				ans+=i+'a'-1;
				return ans;
			} else {
				string nxt=u.nw;
				nxt+=i+'a'-1;
				q.push({nxt,u.step+1});
			}
	} 
	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];
		lim+=s[i].size();
		for(int j=0;j<(int)s[i].size();j++) {
			int u=s[i][j]-'a'+1;
			int v=s[i][(j+1)%((int)s[i].size())]-'a'+1;
			g[u][v]=true;		
		}
	}
	int len=0x3f3f3f3f;
	string ans="";
	for(int i=1;i<=c;i++) {
		string nw_ans=bfs(i);
		if(nw_ans.size()<len&&nw_ans!="!!!") {
			len=nw_ans.size();
			ans=nw_ans;
		}
	}
	if(len==0x3f3f3f3f) cout<<"NO\n";
	cout<<ans<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

1 26
win

output:

a

result:

ok Got unprintable string of length 1

Test #2:

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

input:

3 3
abc
bca
cab

output:

aa

result:

ok Got unprintable string of length 2

Test #3:

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

input:

4 2
aab
bb
a
bab

output:

NO


result:

ok ok, can print any string

Test #4:

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

input:

7 3
c
ba
acc
bcb
ab
bac
ac

output:

aa

result:

wrong answer pa="aa" can be typed by pressing next keys: "3,5"