Submission #1259996

#TimeUsernameProblemLanguageResultExecution timeMemory
1259996SzymonKrzywdaAlternating Current (BOI18_alternating)C++20
0 / 100
3091 ms12220 KiB
#include <iostream> #include <vector> #include <set> using namespace std; using pii = pair<int, int>; #define ff first #define ss second int n, m; bool czy_zawiera(pii a, pii b) { if (b.ss > n) b.ss -= n; if (a.ss > n) a.ss -= n; int typ1 = 0; int typ2 = 0; if (a.ff > a.ss) typ1 = 1; if (b.ff > b.ss) typ2 = 1; if (typ1 == 0 && typ2 == 0) { return (a.ff <= b.ff && a.ss >= b.ss); } if (typ1 == 0 && typ2 == 1) { return b.ss == n && a.ff == 1; } if (typ1 == 1 && typ2 == 0) { return a.ss >= b.ss; } if (typ1 == 1 && typ2 == 1) { return (a.ff <= b.ff && a.ss >= b.ss); } } bool compp(pii & a, pii & b) { return a.first > b.first; } vector<pii> prz; bool check(vector<bool> odp) { vector<vector<int>> sumy(n + 2, vector<int>(2, 0)); vector<pii> prz2 = prz; for (int i = 0; i < m; i++) { if (prz2[i].ss > n) prz2[i].ss -= n; if (prz2[i].ff <= prz2[i].ss) { sumy[prz2[i].ff][odp[i]]++; sumy[prz2[i].ss + 1][odp[i]] --; } else { sumy[prz2[i].ff][odp[i]] ++; sumy[n + 1][odp[i]] --; sumy[1][odp[i]] ++ ; sumy[prz2[i].ss + 1][odp[i]] --; } } for (int i = 1; i <= n; i++) { sumy[i][0] += sumy[i - 1][0]; sumy[i][1] += sumy[i - 1][1]; //cout << sumy[i][0] << ' ' << sumy[i][1] << '\n'; if (sumy[i][0] == 0 || sumy[i][1] == 0) return 0; } return true; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; vector<int> parent(m, -1); prz.resize(m); vector<pii> prz2; for (int i = 0; i < m; i++) { cin >> prz[i].ff >> prz[i].ss; if (prz[i].ff > prz[i].ss) prz[i].ss += n; if (prz[i].ff > prz[i].ss) prz2.push_back({n - prz[i].ff + 1 + prz[i].ss, i}); else prz2.push_back({prz[i].ss - prz[i].ff + 1, i}); } sort(prz2.begin(), prz2.end(), compp); set<pair<pair<int, int>, int>> akt_prz; for (int i = 0; i < m; i++) { int a = prz[prz2[i].ss].ff, b = prz[prz2[i].ss].ss; if (akt_prz.size() == 0) { akt_prz.insert({{a, b}, prz2[i].ss}); continue; } bool dodac = 1; auto wsk = akt_prz.upper_bound({{a, 1e9}, -1}); if (wsk == akt_prz.begin()) wsk = --akt_prz.end(); else wsk--; //cout << (*wsk).ff.ff << ' ' << (*wsk).ff.ss << ' ' << a << ' ' << b << '\n'; if (czy_zawiera((*wsk).ff, {a, b})) { parent[prz2[i].ss] = (*wsk).ss; dodac = 0; } // cout << "NIEXD" << dodac << '\n'; if (dodac) akt_prz.insert({{a, b}, prz2[i].ss}); } //for (int i = 0; i < m; i++) cout << parent[i] << '\n'; vector<int> sumy1(n + 2, 0); for (int i = 0; i < m; i++) { //cout << prz[i].ss + 1 << '\n'; if (prz[i].ss > n) prz[i].ss -= n; if (prz[i].ff <= prz[i].ss) { sumy1[prz[i].ff]++; sumy1[prz[i].ss + 1] --; } else { sumy1[prz[i].ff] ++; sumy1[n + 1] --; sumy1[1] ++ ; sumy1[prz[i].ss + 1] --; } } for (int i = 1; i < n + 2; i++) { sumy1[i] += sumy1[i - 1]; } vector<int> sumy2(n + 2, 0); for (int i = 1; i < n + 2; i++) { sumy2[i] = sumy2[i - 1] + (sumy1[i] >= 3); } //for (int i = 0; i <= n; i++) cout << sumy1[i] << ' '; //cout << '\n'; vector<pair<pair<int, int>, int>> prz3; for (int i = 0; i < m; i++) { if (parent[i] != -1) continue; prz3.push_back({prz[i], i}); } sort(prz3.begin(), prz3.end()); vector<bool> odp(m, 0); //cout << "OH: " << prz3.size() << '\n'; if (prz3.size() % 2 == 0) { int akt = 0; for (int j = 1; j < prz3.size(); j++) { odp[prz3[j].ss] = odp[prz3[j - 1].ss] ^ 1; } for (int i = 0; i < m; i++) { if (parent[i] == -1) continue; odp[i] = odp[parent[i]] ^ 1; } if (check(odp)) { //cout << "ok\n"; for (int val : odp) cout << val; return 0; } } else { prz3.push_back(prz3[0]); for (int i = 0; i < prz3.size() - 1; i++) { //cout << i << ' ' << prz3[i].ff.ff << ' ' << prz3[i].ff.ss << '\n'; odp[prz3[i].ss] = 1; odp[prz3[i + 1].ss % m] = 1; for (int j = i + 2; j < prz3.size(); j++) { odp[prz3[j].ss] = odp[prz3[j - 1].ss] ^ 1; } for (int j = 1; j < i; j++) { odp[prz3[j].ss] = odp[prz3[j - 1].ss] ^ 1; } for (int i = 0; i < m; i++) { if (parent[i] == -1) continue; odp[i] = odp[parent[i]] ^ 1; } if (check(odp)) { //cout << "ok\n"; //return 0; for (int val : odp) cout << val; return 0; } } } cout << "impossible\n"; return 0; }

Compilation message (stderr)

alternating.cpp: In function 'bool czy_zawiera(pii, pii)':
alternating.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...