oj.uz

Submission #711767

# Submission time Handle Problem Language Result Execution time Memory
711767 2023-03-17T12:59:43 Z william950615 Checker (COCI19_checker) C++14
29 / 110
 3000 ms 20168 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 4 ms 324 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 3 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 4 ms 324 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 3 ms 212 KB Output is correct
8 Correct 52 ms 448 KB Output is correct
9 Correct 53 ms 500 KB Output is correct
10 Correct 36 ms 456 KB Output is correct
11 Correct 14 ms 340 KB Output is correct
12 Correct 57 ms 556 KB Output is correct
13 Correct 52 ms 532 KB Output is correct
14 Correct 53 ms 488 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 19428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 20168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 4 ms 324 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 3 ms 212 KB Output is correct
8 Correct 52 ms 448 KB Output is correct
9 Correct 53 ms 500 KB Output is correct
10 Correct 36 ms 456 KB Output is correct
11 Correct 14 ms 340 KB Output is correct
12 Correct 57 ms 556 KB Output is correct
13 Correct 52 ms 532 KB Output is correct
14 Correct 53 ms 488 KB Output is correct
15 Execution timed out 3056 ms 19428 KB Time limit exceeded
16 Halted 0 ms 0 KB -