#683372 (C++17) No.470 Inverse S+T Problem

提出ソース

結果

問題	No.470 Inverse S+T Problem
ユーザー	wunderkammer2
提出日時	2021-07-26 13:39:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	978 ms / 2,000 ms
コード長	5,447 bytes
コンパイル時間	1,687 ms
コンパイル使用メモリ	150,880 KB
実行使用メモリ	153,048 KB
最終ジャッジ日時	2024-06-01 23:08:06
合計ジャッジ時間	5,855 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	959 ms 153,048 KB
testcase_07	AC	978 ms 152,784 KB
testcase_08	AC	958 ms 152,104 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	81 ms 23,696 KB
testcase_29	AC	10 ms 6,944 KB
testcase_30	AC	39 ms 13,568 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<fstream>       //ファイルストリーム（標準入力変更用）
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

//名前
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef map<string, int> msi;
typedef map<string, ll> msll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pllll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;

//定数
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
const int MAXR = 100000;             //10^5:配列の最大のrange

//マクロ
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,e) for(int i=s;i<e;i++)
#define repse(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define in1(x1) cin >> x1
#define in2(x1, x2) cin >> x1 >> x2
#define in3(x1, x2, x3) cin >> x1 >> x2 >> x3
#define in4(x1, x2, x3, x4) cin >> x1 >> x2 >> x3 >> x4
#define in5(x1, x2, x3, x4, x5) cin >> x1 >> x2 >> x3 >> x4 >> x5
#define in6(x1, x2, x3, x4, x5, x6) cin >> x1 >> x2 >> x3 >> x4 >> x5 >> x6
#define inN(x, N) rep(i, N) in1(x[i])
#define outl(x) cout << x << endl
#define out2l(x, y) cout << x << " " << y << endl 

//よく使う関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
inline ll div_ceil(ll a, ll b) { return (a + (b - 1)) / b; }

class TwoSAT {
private:
	const int V;
	vector<vector<int> > G, rG;
	vector<int> ps, cmp;
	void add_edge(int from, int to){
		G[from].push_back(to), rG[to].push_back(from);
	}
	void dfs(int u){
        cmp[u] = 0;
        for(int v : G[u]){
			if(cmp[v] == -1) dfs(v);
		}
		ps.push_back(u);
	}
	void rdfs(int u, int k){
		cmp[u] = k;
		for(int v : rG[u]){
			if(cmp[v] == -1) rdfs(v, k);
		}
	}
	int scc(){
		for(int i = 0; i < 2 * V; ++i){
			if(cmp[i] == -1) dfs(i);
		}
		fill(cmp.begin(), cmp.end(), -1);
		int k = 0;
		for(int i = 2 * V - 1; i >= 0; --i){
			if(cmp[ps[i]] == -1) rdfs(ps[i], k++);
		}
		return k;
	}
 
public:
	vector<int> ans;
	TwoSAT(const int literal_count)
	 	: V(literal_count), G(2 * V), rG(2 * V), cmp(2 * V, -1), ans(V){}
	void add_closure(int x, int y){
		add_edge((x + V) % (2 * V), y), add_edge((y + V) % (2 * V), x);
	}
	void add_closure(int x, bool tx, int y, bool ty)
    {
        if(!tx) x += V;
        if(!ty) y += V;
		add_edge((x + V) % (2 * V), y), add_edge((y + V) % (2 * V), x);
	}
	// 充足可能性判定
	// 真のものは 1,偽のものは 0 が ans に格納される(解の構成)
	bool satisfy(){
		scc();
		for(int i = 0; i < V; i++){
			if(cmp[i] == cmp[V + i]) return false;
			ans[i] = (cmp[i] > cmp[V + i]);
		}
		return true;
	}
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //標準入力をファイルに変更
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());

    int N;
    in1(N);

    vs U(N);
    inN(U, N);

    map<string, vector<pair<int, bool>>> m;

    rep(i, N)
    {
        m[U[i].substr(0, 1)].emplace_back(i, true);
        m[U[i].substr(1, 2)].emplace_back(i, true);
        m[U[i].substr(0, 2)].emplace_back(i, false);
        m[U[i].substr(2, 1)].emplace_back(i, false);
    }

    int M = 4 * N;

    TwoSAT ts(N + M);

    //追加した論理変数の個数
    int pos = 0;

    for(auto [s, v] : m)
    {
        for(int i=0;i<v.size();i++)
        {
            //(v[i]ならばcnt+posが真) <=> not v[i] or cnt+pos
            ts.add_closure(v[i].first, !v[i].second,N + pos, true);
            if(i){
                //(cnt+pos-1が真ならばcnt+posが真) <=> not cnt+pos-1 or cnt+pos
                ts.add_closure(N + pos - 1, false, N + pos, true);
                //not(cnt+pos-1が真かつv[i]) <=> not v[i] or not cnt+pos-1
                ts.add_closure(v[i].first, !v[i].second, N + pos-1, false);
            }
            pos++;
        }
    }

    if(ts.satisfy())
    {
        rep(i, N)
        {
            if(ts.ans[i])
            {
                out2l(U[i].substr(0, 1), U[i].substr(1, 2));
            }
            else
            {
                out2l(U[i].substr(0, 2), U[i].substr(2, 1));
            }
        }
    }
    else
    {
        outl("Impossible");
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード