Not a member of Pastebin yet?
                        Sign Up,
                        it unlocks many cool features!                    
                - #pragma comment(linker, "/STACK:65777216")
 - #include <cstdio>
 - #include <algorithm>
 - #include <memory.h>
 - #define N 55
 - using namespace std;
 - int len[N],g[N][N+N][N+N],a[N][N],t[N],c;
 - inline int mex(){
 - sort(t,t+c);
 - if (t[0]!=0) return 0;
 - for (int i=1;i<c;++i) if (t[i]-t[i-1]>1) return t[i-1]+1;
 - return t[c-1]+1;
 - }
 - void calc(int num,int l,int r){
 - for (int i=l;i<=r;++i){
 - int go=a[num][i],pos;
 - for (pos=l;a[num][pos]<=go && pos<=r;++pos);
 - for (int j=pos;j<=r+1;++j)
 - if (a[num][j]<=go || j==r+1){
 - if (pos<=j-1 && g[num][pos][j-1]==-1) calc(num,pos,j-1);
 - pos=j+1;
 - }
 - }
 - c=0;
 - for (int i=l;i<=r;++i){
 - int go=a[num][i],pos,ans=0;
 - for (pos=l;a[num][pos]<=go && pos<=r;++pos);
 - for (int j=pos;j<=r+1;++j)
 - if (a[num][j]<=go || j==r+1){
 - if (pos<=j-1) ans^=g[num][pos][j-1];
 - pos=j+1;
 - }
 - t[c++]=ans;
 - }
 - g[num][l][r]=mex();
 - }
 - inline bool good(int n,int num,int go){
 - int ans=0;
 - for (int i=1;i<=n;i++) if (i!=num) ans^=g[i][1][len[i]];
 - int pos;
 - for (pos=1;a[num][pos]<=go && pos<=len[num];++pos);
 - for (int j=pos;j<=len[num]+1;++j)
 - if (a[num][j]<=go || j==len[num]+1){
 - if (pos<=j-1) ans^=g[num][pos][j-1];
 - pos=j+1;
 - }
 - return ans==0;
 - }
 - int main(){
 - // freopen("input.txt","r",stdin);
 - int n,ans=0;
 - scanf("%d",&n);
 - for (int i=1;i<=n;++i){
 - scanf("%d",&len[i]);
 - for (int j=1;j<=len[i];++j) scanf("%d",&a[i][j]);
 - }
 - memset(g,255,sizeof(g));
 - for (int i=1;i<=n;++i) for (int j=1;j<=len[i];++j) g[i][j][j]=1;
 - for (int i=1;i<=n;++i) if (g[i][1][len[i]]==-1) calc(i,1,len[i]);
 - for (int i=1;i<=n;++i) ans^=g[i][1][len[i]];
 - if (!ans) puts("S");
 - else {
 - puts("G");
 - for (int i=1;i<=n;++i) for (int j=1;j<=len[i];++j)
 - if (good(n,i,a[i][j])){
 - printf("%d %d\n",i,j);
 - return 0;
 - }
 - }
 - return 0;
 - }
 
Advertisement
 
                    Add Comment                
                
                        Please, Sign In to add comment