#1039947 (D) No.3031 曲面の向き付け

• 問題: No.3031 曲面の向き付け
• ユーザー: ジュ・ビオレ・グレイス
• 提出日時: 2025-01-30 19:11:08
• 言語: D (dmd 2.109.1)
• 結果: WA
• 実行時間: -
• コード長: 2,530 bytes
• コンパイル時間: 755 ms
• コンパイル使用メモリ: 82,128 KB
• 実行使用メモリ: 80,916 KB
• 最終ジャッジ日時: 2025-02-01 22:01:43
• 合計ジャッジ時間: 9,283 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	WA * 4
other	WA * 29

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import std.array, std.conv, std.stdio;
struct Edge {
    // assert(A < B)
    uint P, Q;
}
struct Triangle {
    // assert(A < B && B < C)
    uint A, B, C;
    this (uint a, uint b, uint c) {
        A = a, B = b, C = c;
    }
    
    // X is A, B or C
    // 1: A->B->C, -1: A->C->B
    uint perm(uint X, int orientation) {
        if (orientation == 1) {
            if      (X == A) return B;
            else if (X == B) return C;
            else if (X == C) return A;
            else assert(0);
        }
        else if (orientation == -1) {
            if      (X == B) return A;
            else if (X == C) return B;
            else if (X == A) return C;
            else assert(0);
        }
        else
            assert(0);
    }
}
void main() {
    auto M = readln[0 .. $-1].to!uint;
    
    // orientations
    int[Triangle] orientation;
    // the triangles which has that
    bool[Triangle][Edge] edge_set;
    
    uint ans = M;
    foreach (m; 0 .. M) {
        // read from input
        auto ABC = readln.split.to!(uint[]);
        auto A = ABC[0], B = ABC[1], C = ABC[2];
        assert(A < B && B < C);
        auto triangle = Triangle(A, B, C);
        auto edge1 = Edge(A, B), edge2 = Edge(B, C), edge3 = Edge(A, C);
        int ori1 = 0, ori2 = 0, ori3 = 0;       // 0: any
        // already known
        if (ans < M) {
            continue;
        }
        
        // edge1 already appeared
        if (auto tris = edge1 in edge_set) {
            // one edge is shared by three triangles
            if ((*tris).length >= 2) {
                ans = m;
                continue;
            }
            else {
                auto tri = (*tris).keys[0];
                auto ori = orientation[tri];
                (*tris)[triangle] = true;
                ori1 = tri.perm(A, ori) == B ? -1 : 1;
            }
        }
        else {
            edge_set[edge1] = [triangle: true];
        }
        // edge2 already appeared
        if (auto tris = edge2 in edge_set) {
            // one edge is shared by three triangles
            if ((*tris).length >= 2) {
                ans = m;
                continue;
            }
            else {
                auto tri = tris.keys[0];
                auto ori = orientation[tri];
                (*tris)[triangle] = true;
                ori2 = tri.perm(B, ori) == C ? -1 : 1;
            }
        }
        else {
            edge_set[edge2] = [triangle: true];
        }
        // edge3 already appeared
        if (auto tris = edge3 in edge_set) {
            // one edge is shared by three triangles
            if ((*tris).length >= 2) {
                ans = m;
                continue;
            }
            else {
                auto tri = tris.keys[0];
                auto ori = orientation[tri];
                (*tris)[triangle] = true;
                ori3 = tri.perm(C, ori) == A ? -1 : 1;
            }
        }
        else {
            edge_set[edge3] = [triangle: true];
        }
        
        // check compatibility
        if (ori1 * ori2 < 0 || ori2 * ori3 < 0 || ori3 * ori1 < 0) {
            ans = m;
        }
        else {
            if (ori1 == 1  || ori2 == 1 || ori3 == 1) orientation[triangle] = 1;
            else orientation[triangle] = -1;
        }
    }
    
    ans.writeln;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX