結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
}
0