Submission #9775

#	Time	Username	Problem	Language	Result	Execution time	Memory
9775		pichulia	Solve another chuck (kriii2_S)	C++98	0 / 4	12 ms	73848 KiB

S

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
int n, m;
int a[2003][2003];
int b[2003][2003];
piii aa[400001];
int ss[400001];
int aal;
int c[2003];
int res;
piii ra[3000009];
int al;
int sum;
void print(piii x)
{
	if(x.second == 0){
		printf("rotS %d %d\n",x.first.first+1, x.first.second);
	}
	if(x.second == 1){
		printf("rotR %d %d\n",x.first.first+1, x.first.second);
	}
	if(x.second == 2){
		printf("negR %d\n",x.first.first+1);
	}
	if(x.second == 3){
		printf("negS %d\n",x.first.first+1);
	}
}
bool able(int k)
{
	int i, j;
	for(i=0;i<m;i++)
	{
		if(n*i > k) return false;
		j = k - n*i;
		if(j%m == 0) return true;
	}
	return false;
}
int main()
{
	int i, j, k, l;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
			sum+=a[i][j];
			aa[aal++] = piii(pii(a[i][j],i),j);
		}
	sort(aa,aa+aal);
	for(i=1;i<=aal;i++)
		ss[i] = ss[i-1] + aa[i-1].first.first;
	res = sum;
	int mm = 0;
	int mk = 0;
	for(k=1;k<=n*m; k++)
	{
		if(able(k))
		{
			if(mm < -ss[k])
			{
				mm = -ss[k];
				mk = k;
			}
			else
				break;
		}
	}
	for(k=0;k<mk;k++)
	{
		b[aa[k].first.second][aa[k].second] = 1;
	}
	res = sum + 2*mm;
	if(mk == 0)
	{
		printf("%d 0\n",sum);
		return 0;
	}
    bool flag = true;
	while(mk)
	{
        if(mk < 0) for(i=2;i>0;i++)printf("%d",i);
        if(mk%n==0)flag = false;
		if(flag) // negR
		{
			for(j=0;j<m;j++)
			{
				if(b[0][j] == 1){b[0][j] = 0;continue;}
				for(i=1;i<n;i++)
				{
					if(b[i][j] == 1)
					{
						for(k=0;k<n;k++)
						{
							c[k] = b[(k+i)%n][j];
						}
						for(k=0;k<n;k++)
							b[k][j] = c[k];
						ra[al++] = piii(pii(j,n-i),0);
						b[0][j] = 0;
						break;
					}
				}
				if(i==n)
				{
					for(i=1;i<n;i++)
					{
						for(k=0;k<m;k++)
						{
							if(b[i][k] == 1)
							{
								for(l = 0; l<m;l++)
								{
									c[l] = b[i][(k-j+m+l)%m];
								}
								for(l=0;l<m;l++)
									b[i][l] = c[l];
								ra[al++] = piii(pii(i, m-(m+k-j)%m),1);
								goto L;
							}
						}
					}
					L:
					for(k=0;k<n;k++)
					{
						c[k] = b[(k+i)%n][j];
					}
					for(k=0;k<n;k++)
						b[k][j] = c[k];
					ra[al++] = piii(pii(j,n-i),0);
					b[0][j] = 0;
				}
			}
			ra[al++] = piii(pii(0,0),2);
			mk-=m;
		}
		else
		{
			
			for(i=0;i<n;i++)
			{
				if(b[i][0] == 1){b[i][0] = 0;continue;}
				for(j=1;j<m;j++)
				{
					if(b[i][j] == 1)
					{
						for(k=0;k<m;k++)
						{
							c[k] = b[i][(k+j)%m];
						}
						for(k=0;k<m;k++)
							b[i][k] = c[k];
						ra[al++] = piii(pii(i,m-j),1);
						b[i][0] = 0;
						break;
					}
				}
				if(j==m)
				{
					for(j=1;j<m;j++)
					{
						for(k=0;k<n;k++)
						{
							if(b[k][j] == 1)
							{
								for(l = 0; l<n;l++)
								{
									c[l] = b[(k-i+n+l)%n][j];
								}
								for(l=0;l<n;l++)
									b[l][j] = c[l];
								ra[al++] = piii(pii(j, n-(n+k-i)%n),0);
								goto L2;
							}
						}
					}
					L2:
					for(k=0;k<m;k++)
					{
						c[k] = b[i][(k+j)%m];
					}
					for(k=0;k<m;k++)
						b[i][k] = c[k];
					ra[al++] = piii(pii(i,m-j),1);
					b[i][0] = 0;
				}
			}
			ra[al++] = piii(pii(0,0),3);
			mk -= n;
		}
	}
	printf("%d %d\n",res,al);
	for(i=0;i<al;i++)
		print(ra[i]);
}

• Subtask 1: 0 / 4