Advertisement
Tranvick

Timus_1540

Apr 16th, 2012
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:65777216")
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <memory.h>
  5. #define N 55
  6.  
  7. using namespace std;
  8.  
  9. int len[N],g[N][N+N][N+N],a[N][N],t[N],c;
  10.  
  11. inline int mex(){
  12.     sort(t,t+c);
  13.     if (t[0]!=0) return 0;
  14.     for (int i=1;i<c;++i) if (t[i]-t[i-1]>1) return t[i-1]+1;
  15.     return t[c-1]+1;
  16. }
  17.  
  18. void calc(int num,int l,int r){
  19.     for (int i=l;i<=r;++i){
  20.         int go=a[num][i],pos;
  21.         for (pos=l;a[num][pos]<=go && pos<=r;++pos);
  22.         for (int j=pos;j<=r+1;++j)
  23.             if (a[num][j]<=go || j==r+1){
  24.                 if (pos<=j-1 && g[num][pos][j-1]==-1) calc(num,pos,j-1);
  25.                 pos=j+1;
  26.             }
  27.     }
  28.     c=0;
  29.     for (int i=l;i<=r;++i){
  30.         int go=a[num][i],pos,ans=0;
  31.         for (pos=l;a[num][pos]<=go && pos<=r;++pos);
  32.         for (int j=pos;j<=r+1;++j)
  33.             if (a[num][j]<=go || j==r+1){
  34.                 if (pos<=j-1) ans^=g[num][pos][j-1];
  35.                 pos=j+1;
  36.             }
  37.         t[c++]=ans;
  38.     }
  39.     g[num][l][r]=mex();
  40. }
  41.  
  42. inline bool good(int n,int num,int go){
  43.     int ans=0;
  44.     for (int i=1;i<=n;i++) if (i!=num) ans^=g[i][1][len[i]];
  45.     int pos;
  46.     for (pos=1;a[num][pos]<=go && pos<=len[num];++pos);
  47.     for (int j=pos;j<=len[num]+1;++j)
  48.         if (a[num][j]<=go || j==len[num]+1){
  49.             if (pos<=j-1) ans^=g[num][pos][j-1];
  50.             pos=j+1;
  51.         }
  52.     return ans==0;
  53. }
  54.  
  55. int main(){
  56. //  freopen("input.txt","r",stdin);
  57.     int n,ans=0;
  58.     scanf("%d",&n);
  59.     for (int i=1;i<=n;++i){
  60.         scanf("%d",&len[i]);
  61.         for (int j=1;j<=len[i];++j) scanf("%d",&a[i][j]);
  62.     }
  63.     memset(g,255,sizeof(g));
  64.     for (int i=1;i<=n;++i) for (int j=1;j<=len[i];++j) g[i][j][j]=1;
  65.     for (int i=1;i<=n;++i) if (g[i][1][len[i]]==-1) calc(i,1,len[i]);
  66.     for (int i=1;i<=n;++i) ans^=g[i][1][len[i]];
  67.     if (!ans) puts("S");
  68.     else {
  69.         puts("G");
  70.         for (int i=1;i<=n;++i) for (int j=1;j<=len[i];++j)
  71.             if (good(n,i,a[i][j])){
  72.                 printf("%d %d\n",i,j);
  73.                 return 0;
  74.             }
  75.     }
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement