fork download
copy 
  1. //Twofive - IOI
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <set>
  6. using namespace std;
  7.  
  8. const int MAXN = 100000000;
  9. string ans[26];
  10. string palavra[26];
  11. string maybe[26];
  12. pair<bool,bool> deucerto[26];
  13. bool mark[26];
  14. int n,qtd;
  15. string s;
  16. char c;
  17. set<int> conjunto;
  18.  
  19. bool achapalavras(int letra){
  20.  
  21.     if(letra == 25){
  22.  
  23.         qtd++;
  24.  
  25.         int atual = 25;
  26.         palavra[atual] = (char)('A' + letra - 1);
  27.  
  28.         if(c == 'W'){
  29.  
  30.             bool top = true;
  31.             for(int i=1; i<=25; i++) if(maybe[i] != palavra[i]) top = false;
  32.  
  33.             if(top){
  34.                 cout << qtd << "\n";
  35.                 return true;
  36.             }
  37.  
  38.         }
  39.  
  40.         if(c == 'N'){
  41.             if(qtd == n){
  42.  
  43.                 for(int i=1; i<=25; i++){
  44.                     ans[i] = palavra[i];
  45.                     cout << ans[i];
  46.                 }
  47.                 cout << "\n";
  48.                 return true;
  49.             }
  50.         }
  51.         return false;
  52.     }
  53.  
  54.     /*
  55.     while(!fila.empty()){
  56.         cout << fila.front() << " ";
  57.         aux.push(fila.front());
  58.         fila.pop();
  59.     }
  60.     cout << endl;
  61.  
  62.     while(!aux.empty()){
  63.         fila.push(aux.front());
  64.         aux.pop();
  65.     }
  66.     */
  67.  
  68.     vector<int> aux;
  69.     for(set<int>::iterator it = conjunto.begin(); it != conjunto.end(); it++) aux.push_back(*it);
  70.  
  71.     for(int i=0; i<aux.size(); i++){
  72.  
  73.         int atual = aux[i];
  74.  
  75.         conjunto.erase(atual);
  76.  
  77.         bool ok1 = false, ok2 = false;
  78.         bool daverdade;
  79.  
  80.         if(atual+1 <= 25){
  81.             deucerto[atual+1].first = true;
  82.             if(deucerto[atual+1].first && deucerto[atual+1].second && !mark[atual+1]){
  83.                 mark[atual+1] = true;
  84.                 ok1 = true;
  85.             }
  86.         }
  87.         if(atual+5 <= 25){
  88.             deucerto[atual+5].second = true;
  89.             if(deucerto[atual+5].first && deucerto[atual+5].second && !mark[atual+5]){
  90.                 mark[atual+5] = true;
  91.                 ok2 = true;
  92.             }
  93.         }
  94.  
  95.         palavra[atual] = (char)('A' + letra - 1);
  96.  
  97.         if(ok1 && !ok2){
  98.             conjunto.insert(atual+1);
  99.             daverdade = achapalavras(letra+1);
  100.             conjunto.erase(atual+1);
  101.             mark[atual+1] = false;
  102.         }else if(!ok1 && ok2){
  103.             conjunto.insert(atual+5);
  104.             daverdade = achapalavras(letra+1);
  105.             conjunto.erase(atual+5);
  106.             mark[atual+5] = false;
  107.         }else if(ok1 && ok2){
  108.  
  109.             conjunto.insert(atual+1);
  110.             conjunto.insert(atual+5);
  111.             daverdade = achapalavras(letra+1);
  112.  
  113.             conjunto.erase(atual+1);
  114.             conjunto.erase(atual+5);
  115.  
  116.             mark[atual+1] = mark[atual+5] = false;
  117.  
  118.         }else{
  119.             daverdade = achapalavras(letra+1);
  120.         }
  121.  
  122.         if(daverdade) return true;
  123.  
  124.         conjunto.insert(atual);
  125.     }
  126.  
  127.     return false;
  128. }
  129.  
  130. int main(){
  131.  
  132.     cin >> c;
  133.  
  134.     if(c == 'W'){
  135.         cin >> s;
  136.         for(int i=0; i<s.size(); i++){
  137.             maybe[i+1] = s[i];
  138.         }
  139.     }
  140.     if(c == 'N') cin >> n;
  141.  
  142.     //Inicialização
  143.     for(int i=1; i<=5; i++) deucerto[i].second = true;
  144.     for(int i=1; i<=25; i+=5) deucerto[i].first = true;
  145.  
  146.     mark[1] = true;
  147.     conjunto.insert(1);
  148.     bool sla = achapalavras(1);
  149.  
  150.     return 0;
  151. }
  152.  
Time limit exceeded #stdin #stdout 5s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PIhFcv
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!