結果
問題 | No.470 Inverse S+T Problem |
ユーザー | 🐬hec |
提出日時 | 2016-12-20 04:43:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,421 bytes |
コンパイル時間 | 1,831 ms |
コンパイル使用メモリ | 176,536 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-22 13:26:29 |
合計ジャッジ時間 | 3,409 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>#define _overload(_1,_2,_3,name,...) name#define _rep(i,n) _range(i,0,n)#define _range(i,a,b) for(int i=int(a);i<int(b);++i)#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)#define _rrep(i,n) _rrange(i,n,0)#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)#define _all(arg) begin(arg),end(arg)#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)#define clr(a,b) memset((a),(b),sizeof(a))#define bit(n) (1LL<<(n))#define popcount(n) (__builtin_popcountll(n))using namespace std;template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}using ll=long long;using R=long double;const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}inline R sq(R x){return sqrt(max(x,0.0L));}const int dx[8]={1,0,-1,0,1,-1,-1,1};const int dy[8]={0,1,0,-1,1,1,-1,-1};// Problem Specific Parameter:string s[110];int par[110];int main(void){int n;cin >> n;if(n>52){puts("Impossible");return 0;}rep(i,n) cin >> s[i];rep(i,n) par[i]=-1;rep(i,n){if(par[i]!=-1) continue;rep(j,2){bool ok=true;int tmp[110];rep(k,n) tmp[k]=par[k];tmp[i]=j;queue<int> q;q.push(i);while(ok and !q.empty()){int cur=q.front(); q.pop();string one=s[cur].substr(tmp[cur]?2:0,1);string two=s[cur].substr(tmp[cur]?0:1,2);//cout << cur << " " << one << " " << two << endl;rep(k,n){if(k==cur) continue;int ban=0;if(tmp[k]==0) ban|=1;if(tmp[k]==1) ban|=2;if(s[k].substr(0,1)==one or s[k].substr(1,2)==two) ban|=2;if(s[k].substr(0,2)==two or s[k].substr(2,1)==one) ban|=1;if(ban==3){ok=false;break;}if(ban!=0 and tmp[k]==-1){if(ban==2) tmp[k]=1;if(ban==1) tmp[k]=0;q.push(k);}}}if(ok){rep(k,n) par[k]=tmp[k];break;}par[i]=-1;}if(par[i]==-1){puts("Impossible");return 0;}}rep(i,n){if(par[i]==0)cout << s[i].substr(0,1) << " " << s[i].substr(1,2) << endl;elsecout << s[i].substr(0,2) << " " << s[i].substr(2,1) << endl;}return 0;}