QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#659612#9478. Shift Puzzleucup-team3510#RE 0ms0kbC++143.0kb2024-10-19 20:58:572024-10-19 20:59:01

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 20:59:01]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-19 20:58:57]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int n,c1;
char s[85][85],t[85][85];
struct solver
{
	char s[85][85];
	vector<pii> ans;
	void siftr(int x,bool d=1)
	{printf("siftr(%d)\n",x);
		char c=s[x][n];
		for(int i=n-1;i;--i)s[x][i+1]=s[x][i];
		s[x][1]=c;
		for(int i=1;i<=n;++i)printf("%s\n",s[i]+1);
		if(d)ans.push_back({1,x});
	}
	void siftd(int x,bool d=1)
	{printf("siftd(%d)\n",x);
		char c=s[n][x];
		for(int i=n-1;i;--i)s[i+1][x]=s[i][x];
		s[1][x]=c;
		for(int i=1;i<=n;++i)printf("%s\n",s[i]+1);
		if(d)ans.push_back({2,x});
	}
	bool isa[85];
	vector<pii> va;vector<int> ve;
	int col1(int x)
	{
		int c1=0;
		for(int i=1;i<=n;++i)c1+=s[i][x]=='1';
			return c1;
	}
	int row1(int x)
	{
		int c1=0;
		for(int i=2;i<=n;++i)c1+=s[x][i]=='1';
			return c1;
	}
	void proc()
	{
		printf("=======================proc()\n");
		printf("s:\n");
		for(int i=1;i<=n;++i)printf("%s\n",s[i]+1);
		printf("ve:");for(int x:ve)printf("%d ",x);putchar(10);
		for(auto x:va)
		{
			printf("x:{%d,%d}\n",x.s1,x.s2);

			while(col1(1)<x.s2)
			{
				while(!row1(ve.back()))ve.pop_back();
				int u=ve.back();
				printf("fill with u:%d\n",u);
				while(s[u][1]=='1')siftd(1);
				while(s[u][1]=='0')siftr(u);
			}
			printf("enough ones\n");
			int u=x.s1;
			for(int _=0;_<x.s2;++_)
			{
				while(s[u][1]=='0')siftd(1);
				siftr(u);
			}
		}
	}
}S1,S2;
int main()
{
	freopen("C.in","r",stdin);freopen("C.out","w",stdout);setvbuf(stdout,0,_IONBF,0);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)scanf("%s",t[i]+1);
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	{
		if(s[i][j]=='#')s[i][j]='1';
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)c1+=s[i][j]=='1';
	printf("c1:%d\n",c1);
	if(c1>n*n-c1)
	{
		for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)s[i][j]^=1;
		for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)t[i][j]^=1;
		c1=n*n-c1;
	}
	printf("c1:%d\n",c1);
		int t1=c1;
		for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)S1.s[i][j]=s[i][j];
		int md=0;
		for(int j=n;j;--j)
		{
			if(t1>n)
			{
				S1.va.push_back({j,n});
				t1-=n;
			}
			else
			{
				S1.va.push_back({j,t1});
				md=j;
			}
		}
		for(int j=n;j>=1;--j)S1.ve.push_back(j);
	S1.proc();
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)S2.s[i][j]=t[n-j+1][n-i+1];
	}
	for(int i=1;i<=n;++i)S2.siftr(i,0);
	for(int i=1;i<=n;++i)S2.siftd(i,0);
		t1=c1;
		md=0;
		for(int j=2;j<=n;++j)
		{
			if(t1>n)
			{
				S2.va.push_back({j,n});
				t1-=n;
			}
			else
			{
				S2.va.push_back({j,t1});
				md=j;
			}
		}
		for(int j=2;j<=n;++j)S2.ve.push_back(j);
		S2.ve.push_back(1);
	S2.proc();
	for(int i=1;i<=n;++i)
	{
		for(int _=0;_<n-t1;++_)S2.siftr(i);
	}
	printf("%d\n",(int)S1.ans.size()+(int)S2.ans.size());
	for(pii x:S1.ans)printf("%d %d\n",x.s1,x.s2);
	reverse(S2.ans.begin(),S2.ans.end());
	for(pii x:S2.ans)
	{
		if(x.s2!=1)x.s2=n+2-x.s2;
		printf("%d %d\n",x.s1,x.s2);
	}
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

3
.#.
#.#
.#.
#.#
...
#.#

output:


result: