Submission #362108

#	Time	Username	Problem	Language	Result	Execution time	Memory
362108		limabeans	Checker (COCI19_checker)	C++17	12 / 110	374 ms	15524 KiB

checker

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




const int maxn = 1e6 + 5;

const string BADTRI = "neispravna triangulacija";
const string NOTPAT = "neispravno bojenje";
const string GOOD = "tocno";


struct iv {
    int l,r,c;
    void read() {
	cin>>l>>r>>c;
	--l; --r;
    }
};

int n;
string s;
vector<iv> w;


int dist(int l, int r) {
    return (r-l+n)%n;

}

string solve() {
    w.clear();
    cin>>n;
    cin>>s;
    w.resize(n-3);
    for (int i=0; i<n-3; i++) {
	w[i].read();
    }
    vector<pair<int,int>> nxt(n);
    for (int i=0; i<n; i++) {
	nxt[i].first = (i+1)%n;
	nxt[i].second = int(s[i]-'0');
    }

    vector<pair<pair<int,int>,int>> diags;
    for (auto p: w) {
	diags.push_back({{p.l,p.r},p.c});
	diags.push_back({{p.r,p.l},p.c});
    }

    sort(diags.begin(), diags.end(), [&](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
	return dist(a.first.first,a.first.second) < dist(b.first.first,b.first.second);
    });



    for (int i=0; i<n-2; i++) {
	auto cur = diags[i];
	//cout<<cur.first.first+1<<" "<<cur.first.second+1<<endl;
	
	int a = cur.first.first;
	int b = nxt[a].first;
	int c = cur.first.second;
	if (nxt[b].first != c) {
	    return BADTRI;
	}
	vector<int> colors = {cur.second, nxt[a].second, nxt[b].second};
	if ((int)set<int>(colors.begin(), colors.end()).size() < 3) {
	    return NOTPAT;
	}

	nxt[a] = {c, cur.second};
    }


    return GOOD;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int t;
    cin>>t;
    while (t--) {
	cout<<solve()<<"\n";
    }
    
    
    return 0;
}

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