結果

問題 No.2597 Yet Another Topological Problem
ユーザー daiota
提出日時 2023-12-25 16:05:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,228 bytes
コンパイル時間 1,970 ms
コンパイル使用メモリ 174,692 KB
実行使用メモリ 142,632 KB
最終ジャッジ日時 2024-09-27 14:28:33
合計ジャッジ時間 24,776 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 19 RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define REP(i,n) for(int i=0;i<int(n);i++)

int p,q;
int vi[3000][4000];
vector<vector<P> > b(3000, vector<P>(4000));
int dx[]={1,0,0};
int dy[]={0,1,-1};

bool f=false;
void dfs(int x,int y,int c){

	if(c>250000) return;
	if(abs(y-500)>4*q) return;
	if(x>4*q) return;

	if(x==2*q && y==500){
		f=true;
		return;
	}

	vi[x][y]=1;
	vi[x+2*p][y]=1;



	REP(i,3){
		int X=x+dx[i],Y=y+dy[i];

		if(vi[X][Y]==1 || (X+2*p==2*q && Y==500)) continue;
		b[X][Y].first=x;
		b[X][Y].second=y;
		dfs(X,Y,c+1);

	}
}


vector<P> g(int x,int y){
	vector<P> path;
	path.push_back(P(x,y));
	int s=x,t=y;
	while(1){
		int v=b[s][t].first,u=b[s][t].second;
		path.push_back(P(v,u));

		if(v==0 && u==500) break;

		s=v;
		t=u;
	}

	reverse(path.begin(),path.end());

	return path;

}



int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	int i,j,k;


	cin >> p >> q;


	dfs(0,500,0);  // (0,0)

	if(f){
		vector<P> ans=g(2*q,500);
		int n=ans.size();
		cout <<"Possible" << endl;
		cout << n-1 << endl;
		REP(i,n) cout << ans[i].first << ' ' << ans[i].second-500 << '\n';
	}else{
		cout <<"Imossible" << endl;

	}




	return 0;
}
0