Advertisement
Guest User

1540

a guest
Oct 16th, 2011
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5. map<vector<int>, int> grundi;
  6. int recurse(vector<int> g)
  7. {
  8.     if(g.size() == 0)return 0;
  9.     map<vector<int>, int>::iterator gr_i;
  10.     if((gr_i = grundi.find(g)) != grundi.end())return gr_i->second;
  11.     vector<vector<int> > v;
  12.     vector<bool> ug(g.size());
  13.     vector<bool> used(1000);
  14.     for(int i = 0; i < g.size(); i++)
  15.     {
  16.         if(ug[i])continue;
  17.         v.clear();
  18.         bool sn = true;
  19.         for(int j = 0; j < g.size(); j++)
  20.         {
  21.             if(g[j] <= g[i])
  22.             {
  23.                 if(g[i] == g[j]) ug[j] = true;
  24.                 sn = true;
  25.             }
  26.             else
  27.                 if(sn)
  28.                 {
  29.                     v.push_back(vector<int>(1, g[j]));
  30.                     sn = false;
  31.                 }
  32.                 else
  33.                     v.back().push_back(g[j]);
  34.         }
  35.         int r = 0;
  36.         for(int j = 0; j < v.size(); j++) r = r ^ recurse(v[j]);
  37.         used[r] = true;
  38.     }
  39.     for(int i = 0; i < 1000; i++)if(!used[i])return i;
  40. }
  41. int main()
  42. {
  43.     int k;
  44.     cin >> k;
  45.     vector<vector<int> > a(k);
  46.     for(int i = 0; i < k; i++)
  47.     {
  48.         int n;
  49.         cin >> n;
  50.         a[i].resize(n);
  51.         for(int j = 0; j < n; j++)
  52.             cin >> a[i][j];
  53.     }
  54.     int r = 0;
  55.     for(int i = 0; i < k; i++)
  56.         r ^= recurse(a[i]);
  57.     if(r == 0)cout << "S\n";
  58.     else
  59.     {
  60.         for(int l = 0; l < k; l++)
  61.         {
  62.             int rt = r ^ recurse(a[l]);
  63.             vector<int>& g = a[l];
  64.             vector<bool> ug(g.size());
  65.             vector<vector<int> > v;
  66.             for(int i = 0; i < g.size(); i++)
  67.             {
  68.                 if(ug[i])continue;
  69.                 v.clear();
  70.                 bool sn = true;
  71.                 for(int j = 0; j < g.size(); j++)
  72.                 {
  73.                     if(g[j] <= g[i])
  74.                     {
  75.                         if(g[i] == g[j]) ug[j] = true;
  76.                         sn = true;
  77.                     }
  78.                     else
  79.                         if(sn)
  80.                         {
  81.                             sn = false;
  82.                             v.push_back(vector<int>(1, g[j]));
  83.                         }
  84.                         else
  85.                             v.back().push_back(g[j]);
  86.                 }
  87.                 int r2 = rt;
  88.                 for(int j = 0; j < v.size(); j++) r2 ^= recurse(v[j]);
  89.                 if(r2 == 0)
  90.                 {
  91.                     cout << "G\n" << l + 1 << " " << i + 1 << "\n";
  92.                     return 0;
  93.                 }
  94.             }
  95.         }
  96.     }
  97.     return 0;
  98. }
  99.  
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement