| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133431 |
2019-07-20T16:03:18 Z |
Zex |
Cezar (COCI16_cezar) |
C++11 |
|
4 ms |
376 KB |
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF INT_MAX
#define output for(int i=0;i<26;i++) { for(int j=0;j<26;j++) { cout << adj[i][j] << " "; }cout<<endl; }cout<<endl;
const int maxN = 101;
int N, M;
vector <int> order(maxN);
vector <string> V(maxN);
int inDegree[26];
bool appearsInInput[26];
bool adj[26][26];
bool valid = true;
vector <int> topoSort;
void findDif( string a, string b, char &_a, char &_b ){
int len = min( a.length(), b.length() );
for(int i=0;i<len;i++){
if( a[i] != b[i] ){
_a = a[i]; _b = b[i]; return;
}
}
_a = _b = '~';
}
void connect( string a, string b ){
char _a, _b;
findDif( a, b, _a, _b );
if( _a == '~' ) return;
appearsInInput[_a-97] = appearsInInput[_b-97] = true;
adj[_a-97][_b-97] = true;
inDegree[_b-97]++;
}
bool nonValid( string a, string b ){
if( a.length() <= b.length() ) return false;
return b == a.substr( 0, b.length() ); // a can never be smaller than b
}
int countDistinct(){
int rv = 0;
for(int i=0;i<26;i++) rv += appearsInInput[i];
return rv;
}
void genTopoSort(){
queue <int> q;
while( true ){
for(int i=0;i<26;i++){
if( !inDegree[i] && appearsInInput[i] ) q.push(i);
}
if( q.empty() ) break;
int V;
while( !q.empty() ){
V = q.front();
q.pop();
topoSort.push_back(V);
inDegree[V] = -1;
for(int j=0;j<26;j++){
if( adj[V][j] ) inDegree[j]--;
}
}
}
}
void printRes(){
cout << "DA" << endl;
char key[26]; for(int i=0;i<26;i++) key[i] = '~';
char c = 'a';
string vc = "";
for(int i=0;i<26;i++){
if( appearsInInput[i] ) vc += char(i+97);
else key[i] = char(i+97);
}
// for(int i=0;i<26;i++) cout << key[i]; cout << endl;
sort( vc.begin(), vc.end() );
int x; int idx = 0;
for(int i=0;i<topoSort.size();i++){
int x = topoSort[i];
key[x] = vc[idx++];
}
for(int i=0;i<26;i++) cout << key[i]; cout << endl;
}
int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset( adj, 0, sizeof adj );
memset( inDegree, 0, sizeof inDegree );
memset( appearsInInput, 0, sizeof appearsInInput );
cin >> N;
for(int i=1;i<=N;i++) cin >> V[i];
for(int i=1;i<=N;i++) cin >> order[i];
for(int i=1;i<=N;i++){
for(int j=i+1;j<=N;j++){
if( nonValid( V[order[i]], V[order[j]] ) ) { valid = false; break; }
connect( V[order[i]], V[order[j]] );
} if( !valid ) break;
}
M = countDistinct();
genTopoSort();
if( topoSort.size() != M ) valid = false;
if( !valid ) cout << "NE" << endl;
else printRes();
}
Compilation message
cezar.cpp: In function 'void printRes()':
cezar.cpp:104:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<topoSort.size();i++){
~^~~~~~~~~~~~~~~~
cezar.cpp:109:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=0;i<26;i++) cout << key[i]; cout << endl;
^~~
cezar.cpp:109:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=0;i<26;i++) cout << key[i]; cout << endl;
^~~~
cezar.cpp:91:10: warning: unused variable 'c' [-Wunused-variable]
char c = 'a';
^
cezar.cpp:103:9: warning: unused variable 'x' [-Wunused-variable]
int x; int idx = 0;
^
cezar.cpp: In function 'int main()':
cezar.cpp:135:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( topoSort.size() != M ) valid = false;
~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
