Advertisement
karupayun

tap17/j.cpp

Oct 22nd, 2017
209
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None
  1. //touch {a..m}.in; tee {a..m}.cpp < template.cpp
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define forr(i,a,b) for(int i=(a); i<(b); i++)
  5. #define forn(i,n) forr(i,0,n)
  6. #define sz(c) ((int)c.size())
  7. #define zero(v) memset(v, 0, sizeof(v))
  8. #define forall(it,v) for(auto it=v.begin();it!=v.end();++it)
  9. #define pb push_back
  10. #define fst first
  11. #define snd second
  12. typedef long long ll;
  13. typedef pair<int,int> ii;
  14. #define dforn(i,n) for(int i=n-1; i>=0; i--)
  15. #define dprint(v) cout << #v"=" << v << endl //;)
  16.  
  17. #define INF (1e18+1)
  18. #define N 100
  19. #define M 20
  20.  
  21. map <string, int> mapi;
  22. vector <int> v[N*M];
  23.  
  24. bool cmp (vector <int> v1, vector <int> v2){
  25.     forn (i, (int)v1.size()){
  26.         if (v1[i] < v2[i]) return true;
  27.         if (v1[i] > v2[i]) return false;
  28.     }
  29.     return false;
  30. }
  31.  
  32. bool puedenSerNombres (vector <int> v1, vector <int> v2){
  33.     forn (i, (int)v1.size()){
  34.         if (!(v1[i] ^ v2[i])) return false;
  35.     }
  36.     return true;
  37. }
  38.  
  39. bool todosUnos (vector <int> v){
  40.     forn (i, (int)v.size())
  41.         if (!v[i]) return false;
  42.     return true;
  43. }
  44.  
  45. int main(){
  46.     int n,m;
  47.     cin >> n >> m;
  48.     int contador = 0;
  49.     forn (i,n) forn (j,m){
  50.         string s;
  51.         cin >> s;
  52.         if (mapi.count(s) == 0){
  53.             v[contador].resize(n);
  54.             mapi[s] = contador++;
  55.         }
  56.         int number = mapi[s];
  57.    
  58.         v[number][i] = 1;
  59.     }
  60.         sort(v,v+contador, cmp);
  61.         int i = 0, j = contador - 1;
  62.         bool rta = true;
  63.         while (i <= j){
  64.             if (todosUnos (v[j])) {
  65.                 j--;
  66.             }
  67.             else if (puedenSerNombres (v[i], v[j])){
  68.                 i++;
  69.                 j--;
  70.             }
  71.             else{
  72.                 rta = false;
  73.                 break;
  74.             }
  75.         }
  76.            
  77.         cout << (rta?'S':'N') << endl;
  78.    
  79.     return 0;
  80. }
Advertisement
RAW Paste Data Copied
Advertisement