結果

問題 No.470 Inverse S+T Problem
ユーザー rickytheta
提出日時 2016-12-20 01:03:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,527 bytes
コンパイル時間 2,090 ms
コンパイル使用メモリ 181,692 KB
実行使用メモリ 30,404 KB
最終ジャッジ日時 2024-12-22 13:11:55
合計ジャッジ時間 6,890 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:155:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  155 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;
map<string,vi> S1,S2,T1,T2;
int n;
string u[125252];
string s[125252],t[125252];
const int SS1 = 0, SS2 = 1, TT1 = 2, TT2 = 3;
bool dfs2(int type, int id, string x, vi &used){
  if(type==SS1){
    for(int y:S1[x]){
      if(y==id)continue;
      // ab/c
      if(s[y]!="#"){
        if(s[y].size()==2)continue;
        else return false;
      }
      s[y] = u[y].substr(0,2);
      t[y] = u[y].substr(2,1);
      used.push_back(y);
      if(!dfs2(SS1,y,t[y],used) || !dfs2(TT1,y,t[y],used) ||
         !dfs2(SS2,y,s[y],used) || !dfs2(TT2,y,s[y],used)) return false;
    }
  }else if(type==SS2){
    for(int y:S2[x]){
      if(y==id)continue;
      // a/bc
      if(s[y]!="#"){
        if(s[y].size()==1)continue;
        else return false;
      }
      s[y] = u[y].substr(0,1);
      t[y] = u[y].substr(1,2);
      used.push_back(y);
      if(!dfs2(SS1,y,s[y],used) || !dfs2(TT1,y,s[y],used) ||
         !dfs2(SS2,y,t[y],used) || !dfs2(TT2,y,t[y],used)) return false;
    }
  }else if(type==TT1){
    for(int y:T1[x]){
      if(y==id)continue;
      // a/bc
      if(s[y]!="#"){
        if(s[y].size()==1)continue;
        else return false;
      }
      s[y] = u[y].substr(0,1);
      t[y] = u[y].substr(1,2);
      used.push_back(y);
      if(!dfs2(SS1,y,s[y],used) || !dfs2(TT1,y,s[y],used) ||
         !dfs2(SS2,y,t[y],used) || !dfs2(TT2,y,t[y],used)) return false;
    }
  }else if(type==TT2){
    for(int y:T2[x]){
      if(y==id)continue;
      // ab/c
      if(s[y]!="#"){
        if(s[y].size()==2)continue;
        else return false;
      }
      s[y] = u[y].substr(0,2);
      t[y] = u[y].substr(2,1);
      used.push_back(y);
      if(!dfs2(SS1,y,t[y],used) || !dfs2(TT1,y,t[y],used) ||
         !dfs2(SS2,y,s[y],used) || !dfs2(TT2,y,s[y],used)) return false;
    }
  }
  return true;
}
bool dfs(vi &unused){
  // DEBUG_VEC(unused);
  if(unused.size()==0)return true;
  int id = unused[0];
  string x = u[id];
  vi used;
  bool ok;
  // cut a/bc
  used.push_back(id);
  s[id] = u[id].substr(0,1);
  t[id] = u[id].substr(1,2);
  ok = dfs2(SS1,id,s[id],used) && dfs2(TT1,id,s[id],used) &&
       dfs2(SS2,id,t[id],used) && dfs2(TT2,id,t[id],used);
  if(ok){
    sort(ALL(used));
    vi nxt;
    int it = 0;
    for(int y:unused){
      while(it<used.size() && used[it]<y)it++;
      if(it==used.size() || y!=used[it])nxt.push_back(y);
    }
    ok = dfs(nxt);
  }
  if(ok){
    return true;
  }else{
    for(int y:used)s[y]=t[y]="#";
  }
  used.clear();
  // cut ab/c
  used.push_back(id);
  s[id] = u[id].substr(0,2);
  t[id] = u[id].substr(2,1);
  ok = dfs2(SS1,id,t[id],used) && dfs2(TT1,id,t[id],used) &&
       dfs2(SS2,id,s[id],used) && dfs2(TT2,id,s[id],used);
  if(ok){
    sort(ALL(used));
    vi nxt;
    int it = 0;
    for(int y:unused){
      while(it<used.size() && used[it]<y)it++;
      if(it==used.size() || y!=used[it])nxt.push_back(y);
    }
    ok = dfs(nxt);
  }
  if(ok){
    return true;
  }else{
    for(int y:used)s[y]=t[y]="#";
  }
  return false;
}
int main(){
  scanf("%d",&n);
  REP(i,n)cin>>u[i];
  if(n>=1355){
    puts("Impossible");
    return 0;
  }
  REP(i,n){
    string x = u[i];
    string a = x.substr(0,1);
    string ab = x.substr(0,2);
    string bc = x.substr(1,2);
    string c = x.substr(2,1);
    S1[a].push_back(i);
    S2[ab].push_back(i);
    T1[c].push_back(i);
    T2[bc].push_back(i);
    // S1[a][bc].push_back(i);
    // S2[ab][c].push_back(i);
    // T1[c][ab].push_back(i);
    // T2[bc][a].push_back(i);
  }
  REP(i,n)s[i] = t[i] = "#";
  vi unused(n);
  REP(i,n)unused[i]=i;
  if(dfs(unused)){
    REP(i,n){
      printf("%s %s\n",s[i].c_str(),t[i].c_str());
    }
  }else{
    puts("Impossible");
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0