結果

問題 No.1370 置換門松列
ユーザー maimai
提出日時 2024-11-24 12:27:58
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,777 bytes
コンパイル時間 1,212 ms
コンパイル使用メモリ 84,804 KB
実行使用メモリ 35,076 KB
最終ジャッジ日時 2024-11-24 12:28:02
合計ジャッジ時間 4,914 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 21 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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

/*
2024/11/24
ChatGPT o1-preview
*/
/*
1. 使
2.
3. C++ ""
- - -
##
3 $B = (B_1,B_2,B_3)$ $B$
* $B_1,B_2,B_3$
* 3 $B_2$
N $A_1,...,A_N$ $M$
$X_{A_1}, X_{A_2}, ..., X_{A_N}$ $X_1, X_2, ..., X_M$
    1
* 3
##
$3 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le A_i \le M$
##
No
Yes $X_1, X_2, \ldots, X_M$ $X_i$ $1 \le X_i \le 10^9$
    
##
### 1
```
4 3
1 2 3 1
```
```
Yes
2 3 1
```
$A = (1, 2, 3, 1)$ $X = (2, 3, 1)$ $X_{A_1}, X_{A_2}, X_{A_3}, X_{A_N}$ $2, 3, 1, 2$
    3 $(2, 3, 1)$ $(3, 1, 4)$
$X = (3, 4, 2)$
### 2
```
5 3
1 3 3 3 1
```
```
No
```
No
- - -
*/
// Step 1: Overall Strategy
// We model the problem as a 2-SAT problem. Each unique value in A corresponds to a variable that can be true (High) or false (Low).
// Constraints are derived from the Kadomatsu condition on every continuous subsequence of length 3 in A.
// The problem reduces to checking if the 2-SAT instance is satisfiable, and if so, assigning values to variables accordingly.
// Step 2: Specific Implementation Plan
// - For every length-3 subsequence in A, ensure all elements are distinct; if not, output "No".
// - Map each unique A_i to a variable x_i (True or False).
// - For each subsequence (A_i, A_{i+1}, A_{i+2}), add implications based on the Kadomatsu condition:
// - x_{A_{i+1}} ⇒ ¬x_{A_i}
// - x_{A_{i+1}} ⇒ ¬x_{A_{i+2}}
// - ¬x_{A_{i+1}} ⇒ x_{A_i}
// - ¬x_{A_{i+1}} ⇒ x_{A_{i+2}}
// - Build the implication graph and run a 2-SAT solver using SCCs.
// - Assign actual numeric values to X_i based on the variables' assignments.
// - Ensure assigned values satisfy the Kadomatsu condition.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXM = 100005;
vector<int> graph[2 * MAXM]; // Implication graph
vector<int> rgraph[2 * MAXM]; // Reverse implication graph
vector<int> order; // For order in DFS
bool visited[2 * MAXM]; // For DFS
int component[2 * MAXM]; // Component ID for each node
int assignment[MAXM]; // Truth assignment for variables
void dfs1(int v) {
visited[v] = true;
for (int u : graph[v]) {
if (!visited[u])
dfs1(u);
}
order.push_back(v);
}
void dfs2(int v, int label) {
component[v] = label;
for (int u : rgraph[v]) {
if (component[u] == -1)
dfs2(u, label);
}
}
bool two_sat(int num_vars) {
fill(visited, visited + 2 * num_vars, false);
order.clear();
for (int i = 0; i < 2 * num_vars; ++i) {
if (!visited[i])
dfs1(i);
}
fill(component, component + 2 * num_vars, -1);
int label = 0;
for (int i = 2 * num_vars - 1; i >= 0; --i) {
int v = order[i];
if (component[v] == -1) {
dfs2(v, label++);
}
}
for (int i = 0; i < num_vars; ++i) {
if (component[2 * i] == component[2 * i + 1])
return false; // Unsatisfiable
assignment[i] = component[2 * i] > component[2 * i + 1];
}
return true;
}
void add_implication(int u, int v) {
graph[u].push_back(v);
rgraph[v].push_back(u);
}
void add_clause(int a, bool neg_a, int b, bool neg_b) {
// (¬a ∨ b) corresponds to a ⇒ b
int u = 2 * a + (neg_a ? 1 : 0);
int v = 2 * b + (neg_b ? 1 : 0);
add_implication(u, v);
}
int main() {
int N, M;
cin >> N >> M;
vector<int> A(N);
vector<int> unique_values;
for (int i = 0; i < N; ++i) {
cin >> A[i];
--A[i]; // 0-based indexing
unique_values.push_back(A[i]);
}
sort(unique_values.begin(), unique_values.end());
unique_values.erase(unique(unique_values.begin(), unique_values.end()), unique_values.end());
int num_vars = M;
// Map from value to index
vector<int> value_to_index(M);
for (int idx = 0; idx < M; ++idx) {
value_to_index[idx] = idx;
}
// Step 1: Check for duplicates in any subsequence of length 3
for (int i = 0; i + 2 < N; ++i) {
int a = A[i], b = A[i + 1], c = A[i + 2];
if (a == b || b == c || a == c) {
cout << "No" << endl;
return 0;
}
}
// Step 2: Build the 2-SAT clauses
for (int i = 0; i + 2 < N; ++i) {
int a = A[i], b = A[i + 1], c = A[i + 2];
int va = value_to_index[a];
int vb = value_to_index[b];
int vc = value_to_index[c];
// x_vb ⇒ ¬x_va
add_clause(vb, false, va, true);
// x_vb ⇒ ¬x_vc
add_clause(vb, false, vc, true);
// ¬x_vb ⇒ x_va
add_clause(vb, true, va, false);
// ¬x_vb ⇒ x_vc
add_clause(vb, true, vc, false);
}
// Step 3: Solve the 2-SAT instance
if (!two_sat(num_vars)) {
cout << "No" << endl;
return 0;
}
// Step 4: Assign numeric values to X_i
vector<int> X(M);
for (int i = 0; i < M; ++i) {
if (assignment[i]) {
X[i] = 200000000 + i; // High
} else {
X[i] = 100000000 + i; // Low
}
}
// Output result
cout << "Yes" << endl;
for (int i = 0; i < M; ++i) {
cout << X[i] << (i + 1 < M ? ' ' : '\n');
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0