// Checker for problem G // Author: Bartosz Walczak // Second cmdline argument should be a hint (not an output of a model solution) #include #include #include #include #include using namespace std; const char* check(vector> S, int v, vector> T) { int max_begin = T[0].first; for (int i=1; i<(int)T.size(); ++i) { if (T[i].second < max_begin) return "wrong chronology"; max_begin = max(max_begin, T[i].first); } vector>> events; for (int i=0; i<(int)T.size(); ++i) { events.push_back(make_pair(T[i].first, make_pair(0, i))); events.push_back(make_pair(T[i].second, make_pair(1, i))); } sort(S.begin(), S.end()); sort(T.begin(), T.end()); if (S != T) return "wrong set of intervals"; sort(events.begin(), events.end()); set ac; for (auto const& e : events) { if (e.second.first == 0) { ac.insert(e.second.second); int span = *ac.rbegin() - *ac.begin(); if (span > v) return "bandwidth greater than declared"; } else ac.erase(e.second.second); } return nullptr; } int main(int argc, char** argv) { FILE* in = fopen(argv[1], "r"); FILE* hint = fopen(argv[2], "r"); FILE* out = fopen(argv[3], "r"); int all; fscanf(in, "%d", &all); int bad=0, first; const char* msg; for (int t=1; t<=all; ++t) { int n; fscanf(in, "%d", &n); vector> S(n); for (int i=0; i> T(n); for (int i=0; ih) res = "bandwidth greater than optimal"; if (o0) { printf("Bad answers: %d/%d (%.2f%%)\n", bad, all, 100.0*bad/all); printf("First bad answer: Test #%d: %s\n", first, msg); return 1; } printf("OK.\n"); return 0; }