oj.uz

Submission #91147

# Submission time Handle Problem Language Result Execution time Memory
91147 2018-12-26T11:28:31 Z nikolapesic2802 Cezar (COCI16_cezar) C++14
30 / 100
 2 ms 636 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 508 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 2 ms 620 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 636 KB Output isn't correct
2 Halted 0 ms 0 KB -