Submission #222406

#	Time	Username	Problem	Language	Result	Execution time	Memory
222406		oolimry	Checker (COCI19_checker)	C++14	110 / 110	969 ms	64856 KiB

checker

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
struct bracket{
	int pos; int other; bool open; int colour;
};
bool comp(bracket a, bracket b){
	if(a.pos != b.pos) return a.pos < b.pos;
	
	if(a.open && !b.open) return false;
	if(!a.open && b.open) return true;
	
	if(a.open){
		return a.other > b.other;
	}
	else{
		return a.other > b.other;
	}
}

void notTriangle(){
	cout << "neispravna triangulacija";
	exit(0);
}

map<ii, int> Colour;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	int ST; cin >> ST;
	
	int n; cin >> n;
	string S; cin >> S;
	
	vector<bracket> B;
	
	for(int i = 0;i < n;i++){
		int l = i+1;
		int r = i+2;
		if(r == n+1) r = 1;
		if(l > r) swap(l,r);
		int c = S[i] - '0';
		
		B.push_back({l,r,true,c});
		B.push_back({r,l,false,c});
		Colour[ii(l,r)] = c;
		Colour[ii(r,l)] = c;
	}
	
	for(int i = 0;i < n-3;i++){
		int l, r, c; cin >> l >> r >> c;
		if(l > r) swap(l,r);
		Colour[ii(l,r)] = c;
		Colour[ii(r,l)] = c;
		B.push_back({l,r,true,c});
		B.push_back({r,l,false,c});
	}
	
	sort(B.begin(),B.end(),comp);
	
	bool xxxxxxxxxxxxxxxxxxxxxxx = false;
	bracket pre = {0,0,0,0};
	stack<ii> s;
	for(bracket b : B){		
		//cout << b.pos << " " << b.other << " " << b.open << " " << b.colour << endl;
		
		if(b.open){
			s.push(ii(b.pos,b.other));
			
			if(pre.open){
				int x = b.pos;
				int y = pre.other;
				int z = b.other;
				
				set<int> CCC;
				CCC.insert(Colour[ii(x,y)]);
				CCC.insert(Colour[ii(x,z)]);
				CCC.insert(Colour[ii(z,y)]);
				
				//cout << x << " " << y << " " << z << "\n";
				
				if(CCC.size() != 3) xxxxxxxxxxxxxxxxxxxxxxx = true;
			}
		}
		else{
			ii t = s.top();
			if(t.first != b.other && t.second != b.pos){
				notTriangle();
			}
			else s.pop();
		}
		
		pre = b;
		
	}
	
	
	
	
	if(xxxxxxxxxxxxxxxxxxxxxxx) cout << "neispravno bojenje";
	else cout << "tocno";
	
}

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