Submission #219456

#TimeUsernameProblemLanguageResultExecution timeMemory
219456VimmerSkandi (COCI20_skandi)C++14
18 / 110
24 ms1792 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define F first #define S second #define sz(x) int(x.size()) #define pb push_back #define N 75005 #define M ll(1e9 + 7) using namespace std; typedef long double ld; typedef long long ll; typedef short int si; int idr[501][501]; pair <int, int> conv[25005]; int a[25005][2]; vector <int> gr[25005]; vector <pair <int, pair <int, int> > > pr; int main() { ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; string s[n]; int id = 0; for (int i = 0; i < n; i++) {cin >> s[i]; for (int j = 0; j < m; j++) {idr[i][j] = id++; conv[idr[i][j]] = {i, j};} } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { id = idr[i][j]; int y = j + 1; if (s[i][j] != '1') continue; while (y < m && s[i][y] == '0') {gr[idr[i][y]].pb(sz(pr)); y++;} a[id][0] = y - j - 1; y = i + 1; while (y < n && s[y][j] == '0') {gr[idr[y][j]].pb(sz(pr) + 1); y++;} a[id][1] = y - i - 1; pr.pb({a[id][0], {0, id}}); pr.pb({a[id][1], {1, id}}); } bool mk[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) mk[i][j] = s[i][j] - '0'; vector <pair <int, pair <int, int> > > g; g.clear(); while (1) { int mx = 0, tp, id, mt = 1e9, mkr = 1e9; for (auto it : pr) { if (it.F == 0) continue; int kl = 0, lst = it.F; set <int> se; se.clear(); if (it.S.F == 0) { int y = conv[it.S.S].S + 1, x = conv[it.S.S].F; while (y < m && s[x][y] == '0') { if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) {pr[itr].F--; if (pr[itr].F == 0) kl++; se.insert(itr); } y++; } } else { int y = conv[it.S.S].S, x = conv[it.S.S].F + 1; while (x < n && s[x][y] == '0') { if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) {pr[itr].F--; if (pr[itr].F == 0) kl++; se.insert(itr);} x++; } } if (mx < kl) { mx = kl; tp = it.S.F; id = it.S.S; mt = lst; mkr = sz(se); } if (mx == kl && mt < lst) { mx = kl; tp = it.S.F; id = it.S.S; mt = lst; mkr = sz(se); } if (mx == kl && mt == lst && mkr < sz(se)) { mx = kl; tp = it.S.F; id = it.S.S; mt = lst; mkr = sz(se); } if (it.S.F == 0) { int y = conv[it.S.S].S + 1, x = conv[it.S.S].F; while (y < m && s[x][y] == '0') { if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F++; y++; } } else { int y = conv[it.S.S].S, x = conv[it.S.S].F + 1; while (x < n && s[x][y] == '0') { if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F++; x++; } } } if (mx == 0) break; g.pb({tp, {conv[id].F, conv[id].S}}); if (tp == 0) { int y = conv[id].S + 1, x = conv[id].F; while (y < m && s[x][y] == '0') { if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F--; mk[x][y] = 1; y++; } } else { int y = conv[id].S, x = conv[id].F + 1; while (x < n && s[x][y] == '0') { if (!mk[x][y]) for (auto itr : gr[idr[x][y]]) pr[itr].F--; mk[x][y] = 1; x++; } } } cout << sz(g) << endl; for (auto it : g) cout << it.S.F + 1 << " " << it.S.S + 1 << " " << (it.F == 0 ? "DESNO" : "DOLJE") << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...