Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- using namespace std;
- map<vector<int>, int> grundi;
- int recurse(vector<int> g)
- {
- if(g.size() == 0)return 0;
- map<vector<int>, int>::iterator gr_i;
- if((gr_i = grundi.find(g)) != grundi.end())return gr_i->second;
- vector<vector<int> > v;
- vector<bool> ug(g.size());
- vector<bool> used(1000);
- for(int i = 0; i < g.size(); i++)
- {
- if(ug[i])continue;
- v.clear();
- bool sn = true;
- for(int j = 0; j < g.size(); j++)
- {
- if(g[j] <= g[i])
- {
- if(g[i] == g[j]) ug[j] = true;
- sn = true;
- }
- else
- if(sn)
- {
- v.push_back(vector<int>(1, g[j]));
- sn = false;
- }
- else
- v.back().push_back(g[j]);
- }
- int r = 0;
- for(int j = 0; j < v.size(); j++) r = r ^ recurse(v[j]);
- used[r] = true;
- }
- for(int i = 0; i < 1000; i++)if(!used[i])return i;
- }
- int main()
- {
- int k;
- cin >> k;
- vector<vector<int> > a(k);
- for(int i = 0; i < k; i++)
- {
- int n;
- cin >> n;
- a[i].resize(n);
- for(int j = 0; j < n; j++)
- cin >> a[i][j];
- }
- int r = 0;
- for(int i = 0; i < k; i++)
- r ^= recurse(a[i]);
- if(r == 0)cout << "S\n";
- else
- {
- for(int l = 0; l < k; l++)
- {
- int rt = r ^ recurse(a[l]);
- vector<int>& g = a[l];
- vector<bool> ug(g.size());
- vector<vector<int> > v;
- for(int i = 0; i < g.size(); i++)
- {
- if(ug[i])continue;
- v.clear();
- bool sn = true;
- for(int j = 0; j < g.size(); j++)
- {
- if(g[j] <= g[i])
- {
- if(g[i] == g[j]) ug[j] = true;
- sn = true;
- }
- else
- if(sn)
- {
- sn = false;
- v.push_back(vector<int>(1, g[j]));
- }
- else
- v.back().push_back(g[j]);
- }
- int r2 = rt;
- for(int j = 0; j < v.size(); j++) r2 ^= recurse(v[j]);
- if(r2 == 0)
- {
- cout << "G\n" << l + 1 << " " << i + 1 << "\n";
- return 0;
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement