Submission #91147

#	Time	Username	Problem	Language	Result	Execution time	Memory
91147		nikolapesic2802	Cezar (COCI16_cezar)	C++14	30 / 100	2 ms	636 KiB

cezar

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

string s[111];

int o[30][30];
int p[111];

void nie(){
	cout<<"NE"<<endl;
	exit(0);
}

vector<int> g[30];
int ec[30];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>s[i];
	}
	for (int i=1;i<=n;i++){
		int pp;
		cin>>pp;
		p[pp]=i;
	}
	for (int i=1;i<=n;i++){
		for (int ii=i+1;ii<=n;ii++){
			int f=0;
			for (int j=0;j<(int)s[i].size()&&j<(int)s[ii].size();j++){
				if (s[i][j]!=s[ii][j]){
					f=1;
					if (p[i]<p[ii]){
						if (o[s[i][j]-'a'][s[ii][j]-'a']==-1){
							nie();
						}
						else{
							o[s[i][j]-'a'][s[ii][j]-'a']=1;
							o[s[ii][j]-'a'][s[i][j]-'a']=-1;
						}
					}
					else{
						if (o[s[i][j]-'a'][s[ii][j]-'a']==1){
							nie();
						}
						else{
							o[s[i][j]-'a'][s[ii][j]-'a']=-1;
							o[s[ii][j]-'a'][s[i][j]-'a']=1;
						}
					}
					break;
				}
			}
			if (f==0){
				if (s[i].size()>s[ii].size()&&p[i]<p[ii]) nie();
				if (s[i].size()<s[ii].size()&&p[i]>p[ii]) nie();
			}
		}
	}
	cout<<"DA"<<endl;
	for (int i=0;i<26;i++){
		for (int ii=0;ii<26;ii++){
			if (o[i][ii]==1) {
				g[i].push_back(ii);
				ec[ii]++;
			}
		}
	}
	queue<int> topo;
	for (int i=0;i<26;i++){
		if (ec[i]==0) topo.push(i);
	}
	string v;
	while (!topo.empty()){
		int x=topo.front();
		topo.pop();
		v+=(char)('a'+x);
		for (int nx:g[x]){
			ec[nx]--;
			if (ec[nx]==0){
				topo.push(nx);
			}
		}
	}
	if (v.size()!=26){
		nie();
	}
	string vv;
	for (int i=0;i<26;i++){
		vv+=' ';
	}
	for (int i=0;i<26;i++){
		vv[v[i]-'a']=(char)('a'+i);
	}
	cout<<vv<<endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10