結果

問題 No.470 Inverse S+T Problem
ユーザー rickythetarickytheta
提出日時 2016-12-20 01:03:08
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,527 bytes
コンパイル時間 1,762 ms
コンパイル使用メモリ 182,084 KB
実行使用メモリ 22,340 KB
最終ジャッジ日時 2024-06-01 22:29:03
合計ジャッジ時間 5,945 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
22,340 KB
testcase_01 AC 5 ms
15,264 KB
testcase_02 AC 4 ms
15,264 KB
testcase_03 AC 6 ms
15,268 KB
testcase_04 AC 4 ms
15,392 KB
testcase_05 AC 4 ms
15,360 KB
testcase_06 AC 17 ms
15,268 KB
testcase_07 AC 17 ms
15,168 KB
testcase_08 AC 17 ms
15,264 KB
testcase_09 AC 4 ms
15,384 KB
testcase_10 AC 4 ms
15,392 KB
testcase_11 AC 4 ms
15,392 KB
testcase_12 AC 5 ms
15,392 KB
testcase_13 AC 4 ms
15,396 KB
testcase_14 AC 5 ms
15,388 KB
testcase_15 AC 4 ms
15,188 KB
testcase_16 AC 4 ms
15,388 KB
testcase_17 AC 5 ms
15,388 KB
testcase_18 AC 4 ms
15,388 KB
testcase_19 AC 4 ms
15,260 KB
testcase_20 AC 5 ms
15,392 KB
testcase_21 AC 5 ms
15,392 KB
testcase_22 AC 5 ms
15,264 KB
testcase_23 AC 5 ms
15,392 KB
testcase_24 AC 5 ms
15,264 KB
testcase_25 AC 5 ms
15,264 KB
testcase_26 TLE -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0