Submission #711767

#	Time	Username	Problem	Language	Result	Execution time	Memory
711767		william950615	Checker (COCI19_checker)	C++14	29 / 110	3056 ms	20168 KiB

checker

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define mkp make_pair
#define REP(i,n, ...) for( int i = (0), ##__VA_ARGS__; i < n; ++ i)
#define FOR(i,a,b,...) for (int i = (a), ##__VA_ARGS__; i <= (b); ++i)
#define RFOR(i,a,b,...) for (int i = (a), ##__VA_ARGS__; i >= (b); --i)

#define SZ(x) ((int)x.size())
#define MEM(x) memset(x, 0, sizeof(x))
#define ALL(x) begin(x), end(x)
#define iter(x,a) begin(x)+a, end(x)
#define DEBUG
#ifdef DEBUG
	template<typename T> void _DO(T&&x){cerr << x << '\n';}
	template<typename A, typename ...B> void _DO(A&&a, B&&...b){cerr<<a<<','; _DO(b...);}
	#define de(...) do{\
		fprintf(stderr, "%s-%d(%s):", __func__, __LINE__, #__VA_ARGS__);\
		_DO(__VA_ARGS__);\
	}while(0);
#else
	#define de(...)
#endif

template<typename T>
using V = vector<T>;
typedef long long ll;
typedef pair<int,int> pii;

constexpr int mxN = 2e5+1;

inline void solve() {
	int testcase = 0;
	cin >> testcase;
	int N; cin >> N;
	V< pair<int,int> > vc(N);
	REP(i,N) {
		char c;
		cin >> c;
		vc[ i ] = mkp( (i+1)%N, c-'0' );

	}
	V<array<int,3>> op(N-3);
	REP(i,N-3) {
		cin >> op[i][0] >> op[i][1] >> op[i][2];
		--op[i][0], --op[i][1];
		if( op[i][0] > op[i][1] ) swap( op[i][0], op[i][1]);
	}

	sort( ALL(op), [&]( array<int,3>&a, array<int,3>&b) {
			return min((a[0]-a[1]+N)%N, (a[1]-a[0]+N)%N) < min((b[0]-b[1]+N)%N, (b[1]-b[0]+N)%N);
			});

	int ans = 2; 
	auto getPos = [&]( int cur ) {
		return cur == -1 ? mkp(-1,-1) : vc[ cur ];
	};
	/*
	for( auto &i : op ) {
		cout << i[0] << ' ' << i[1] << ' '  << i[2]  << ' ' << (i[0]-i[1]+N)%N << '\n';
	}
	de( ans );
	*/
	REP(i,N-3) {
		auto d = op[ i ];
		if( getPos( getPos( d[1] ).F ).F == d[0 ] ) swap( d[1], d[0] );
		const auto Cur = getPos( d[0] ); 
		const auto Nxt = getPos( Cur.F );
		de( d[0], d[1], d[2], Cur.F, Nxt.F, ans );
		if( Nxt.F == d[1]) {
			int v = d[2] + Cur.S + Nxt.S;
			de( v, d[2], Cur.S, Nxt.S );
			if( v != 6 ) ans = 1;
			vc[ Cur.F ]	= mkp( -1, -1 );
			vc[ d[0] ] = mkp(Nxt.F, d[2]);;
		}
		else {
			ans = 0;
			break;
		}
	}
	cout << (ans == 0 ? "neispravna triangulacija":  ans == 1 ? "neispravno bojenje": "tocno")  <<'\n';
}
int main () {
	int T = 1;
#ifdef Local
	cin >> T;
#endif
	while(T--) solve();
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35