提出 #2004075


ソースコード 拡げる

Copy
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 105;
const int INF = 1e9;

int A,B;
int d[11][11];
int f[N][N];
int m,ed[N*4][3];
bool bz[11][11];
bool v[N][N];
int n;
int id0[N],id1[N],S,T;

int main(){
	A=get();B=get();
	fo(i,1,A)fo(j,1,B)d[i][j]=get();
	fo(i,0,100)
		fo(j,0,100){
			f[i][j]=-INF;
			fo(x,1,A)
				fo(y,1,B)
				f[i][j]=max(f[i][j],d[x][y]-x*i-y*j);
		}
	int cnt=0;
	S=n=1;
	fo(i,0,100)id0[i]=++n;
	fo(i,0,100)id1[i]=++n;
	T=++n;
	ed[m=1][0]=S;ed[1][1]=id0[0];ed[1][0]=0;
	fo(i,0,99){
		m++;
		ed[m][0]=id0[i];ed[m][1]=id0[i+1];ed[m][2]=-1;
	}
	fo(i,0,99){
		m++;
		ed[m][0]=id1[i+1];ed[m][1]=id1[i];ed[m][2]=-2;
	}
	m++;
	ed[m][0]=id1[0];ed[m][1]=T;ed[m][2]=0;
	while(cnt<A*B){
		bool pd=0;
		fo(i,0,100){
			fo(j,0,100)
			if (!v[i][j]&&f[i][j]<=100&&f[i][j]>=0){
				int ct=0;
				fo(x,1,A)
					fo(y,1,B)
					if (!bz[x][y]&&d[x][y]-x*i-y*j==f[i][j])ct++;
				if (ct){
					pd=1;
					fo(x,1,A)
						fo(y,1,B)
						if (d[x][y]-x*i-y*j==f[i][j])bz[x][y]=1;
					ed[++m][0]=id0[i];ed[m][1]=id1[j];ed[m][2]=f[i][j];
					cnt=cnt+ct;
					break;
				}
				else v[i][j]=1;
			}
			if (pd)break;
		}
		if (!pd)break;
	}
	if (cnt!=A*B)printf("Impossible\n");
	else{
		printf("Possbile\n");
		printf("%d %d\n",n,m);
		fo(i,1,m){
			printf("%d %d ",ed[i][0],ed[i][1]);
			if (ed[i][2]==-1)printf("X\n");
			if (ed[i][2]==-2)printf("Y\n");
			if (ed[i][2]>=0)printf("%d\n",ed[i][2]);
		}
		printf("%d %d\n",S,T);
	}
	return 0;
}

提出情報

提出日時
問題 E - GraphXY
ユーザ samjia2000
言語 C++14 (GCC 5.4.1)
得点 0
コード長 2041 Byte
結果 WA
実行時間 3 ms
メモリ 256 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 900
結果
AC × 1
WA × 1
AC × 38
WA × 72
セット名 テストケース
Sample 0_000.txt, 0_001.txt
All 0_000.txt, 0_001.txt, 1_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt
ケース名 結果 実行時間 メモリ
0_000.txt WA 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
1_002.txt WA 2 ms 256 KB
1_003.txt AC 3 ms 256 KB
1_004.txt WA 2 ms 256 KB
1_005.txt WA 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt WA 1 ms 256 KB
1_009.txt WA 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt WA 1 ms 256 KB
1_013.txt WA 1 ms 256 KB
1_014.txt WA 2 ms 256 KB
1_015.txt AC 2 ms 256 KB
1_016.txt AC 2 ms 256 KB
1_017.txt AC 2 ms 256 KB
1_018.txt AC 2 ms 256 KB
1_019.txt AC 2 ms 256 KB
1_020.txt WA 1 ms 256 KB
1_021.txt WA 1 ms 256 KB
1_022.txt WA 1 ms 256 KB
1_023.txt WA 1 ms 256 KB
1_024.txt WA 1 ms 256 KB
1_025.txt WA 1 ms 256 KB
1_026.txt WA 1 ms 256 KB
1_027.txt WA 1 ms 256 KB
1_028.txt WA 1 ms 256 KB
1_029.txt WA 1 ms 256 KB
1_030.txt WA 1 ms 256 KB
1_031.txt WA 1 ms 256 KB
1_032.txt WA 1 ms 256 KB
1_033.txt WA 1 ms 256 KB
1_034.txt WA 1 ms 256 KB
1_035.txt WA 1 ms 256 KB
1_036.txt WA 1 ms 256 KB
1_037.txt WA 1 ms 256 KB
1_038.txt WA 1 ms 256 KB
1_039.txt WA 1 ms 256 KB
1_040.txt WA 1 ms 256 KB
1_041.txt WA 1 ms 256 KB
1_042.txt WA 1 ms 256 KB
1_043.txt WA 1 ms 256 KB
1_044.txt WA 1 ms 256 KB
1_045.txt WA 2 ms 256 KB
1_046.txt WA 2 ms 256 KB
1_047.txt WA 2 ms 256 KB
1_048.txt WA 2 ms 256 KB
1_049.txt WA 2 ms 256 KB
1_050.txt WA 1 ms 256 KB
1_051.txt WA 1 ms 256 KB
1_052.txt WA 1 ms 256 KB
1_053.txt WA 1 ms 256 KB
1_054.txt WA 1 ms 256 KB
1_055.txt WA 2 ms 256 KB
1_056.txt WA 2 ms 256 KB
1_057.txt WA 2 ms 256 KB
1_058.txt WA 2 ms 256 KB
1_059.txt WA 2 ms 256 KB
1_060.txt WA 2 ms 256 KB
1_061.txt WA 2 ms 256 KB
1_062.txt WA 2 ms 256 KB
1_063.txt WA 2 ms 256 KB
1_064.txt WA 2 ms 256 KB
1_065.txt WA 1 ms 256 KB
1_066.txt WA 1 ms 256 KB
1_067.txt WA 1 ms 256 KB
1_068.txt WA 1 ms 256 KB
1_069.txt WA 1 ms 256 KB
1_070.txt AC 1 ms 256 KB
1_071.txt WA 1 ms 256 KB
1_072.txt WA 1 ms 256 KB
1_073.txt WA 1 ms 256 KB
1_074.txt WA 1 ms 256 KB
1_075.txt AC 1 ms 256 KB
1_076.txt AC 1 ms 256 KB
1_077.txt AC 1 ms 256 KB
1_078.txt AC 1 ms 256 KB
1_079.txt AC 1 ms 256 KB
1_080.txt WA 1 ms 256 KB
1_081.txt AC 1 ms 256 KB
1_082.txt WA 1 ms 256 KB
1_083.txt AC 1 ms 256 KB
1_084.txt WA 1 ms 256 KB
1_085.txt AC 1 ms 256 KB
1_086.txt WA 1 ms 256 KB
1_087.txt AC 1 ms 256 KB
1_088.txt WA 1 ms 256 KB
1_089.txt AC 1 ms 256 KB
1_090.txt AC 2 ms 256 KB
1_091.txt AC 2 ms 256 KB
1_092.txt AC 2 ms 256 KB
1_093.txt AC 2 ms 256 KB
1_094.txt AC 2 ms 256 KB
1_095.txt AC 1 ms 256 KB
1_096.txt AC 1 ms 256 KB
1_097.txt WA 1 ms 256 KB
1_098.txt WA 1 ms 256 KB
1_099.txt WA 1 ms 256 KB
1_100.txt AC 2 ms 256 KB
1_101.txt AC 2 ms 256 KB
1_102.txt AC 2 ms 256 KB
1_103.txt WA 2 ms 256 KB
1_104.txt AC 2 ms 256 KB
1_105.txt AC 2 ms 256 KB
1_106.txt AC 2 ms 256 KB
1_107.txt AC 2 ms 256 KB
1_108.txt AC 2 ms 256 KB
1_109.txt AC 2 ms 256 KB
for_sample.txt WA 1 ms 256 KB