Submission #119866

#TimeUsernameProblemLanguageResultExecution timeMemory
119866tutisTrapezi (COI17_trapezi)C++17
6 / 100
1081 ms384 KiB
/*input 2 0000. 0000000 ..00.0. .0000 */ #pragma GCC optimize ("O3") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; struct grupe { int x, y, z; bool reikia = false; }; vector<grupe>xx; vector<char>col; int kiek = 0; vector<int>adj[1000]; vector<int>kaim[1000]; bool ieskom(int i) { if (kiek == 0) return true; if (i == (int)xx.size()) return false; bool ok = true; for (int j : kaim[i]) { if (xx[j].reikia == true) ok = false; } if (ok) { xx[i].reikia = true; kiek -= 3; if (ieskom(i + 1)) return true; kiek += 3; xx[i].reikia = false; } return ieskom(i + 1); } int main() { int n; cin >> n; string s[2 * n]; for (int i = 0; i < 2 * n; i++) cin >> s[i]; vector<int>id[2 * n]; int timer = 0; for (int i = 0; i < 2 * n; i++) for (char &c : s[i]) { id[i].push_back(timer++); if (c == '0') { kiek++; c = '1'; } col.push_back(c); } for (int i = 0; i < 2 * n; i++) { for (int t = 0; t + 1 < (int)id[i].size(); t++) { int x = id[i][t]; int y = id[i][t + 1]; adj[x].push_back(y); adj[y].push_back(x); } } for (int i = 0; i <= n - 2; i++) { for (int t = 0; t < (int)id[i].size(); t += 2) { int x = id[i][t]; int y = id[i + 1][t + 1]; adj[x].push_back(y); adj[y].push_back(x); } } for (int t = 0; t < (int)id[n - 1].size(); t += 2) { int x = id[n - 1][t]; int y = id[n][t]; adj[x].push_back(y); adj[y].push_back(x); } for (int i = n + 1; i < 2 * n; i++) { for (int t = 0; t < (int)id[i].size(); t += 2) { int x = id[i][t]; int y = id[i - 1][t + 1]; adj[x].push_back(y); adj[y].push_back(x); } } for (int i = 1; i < timer; i++) { for (int j : adj[i]) { for (int k : adj[i]) { if (j < k) { grupe a; a.x = i; a.y = j; a.z = k; if (col[a.x] == '1' && col[a.y] == '1' && col[a.z] == '1') xx.push_back(a); } } } } random_shuffle(xx.begin(), xx.end()); for (int i = 0; i < (int)xx.size(); i++) { for (int j = 0; j < (int)xx.size(); j++) { if ( xx[i].x == xx[j].x || xx[i].x == xx[j].y || xx[i].x == xx[j].z || xx[i].y == xx[j].x || xx[i].y == xx[j].y || xx[i].y == xx[j].z || xx[i].z == xx[j].x || xx[i].z == xx[j].y || xx[i].z == xx[j].z ) kaim[i].push_back(j); } } if (ieskom(0)) { for (grupe a : xx) { if (a.reikia == false) continue; set<int>aplink; for (int i : {a.x, a.y, a.z}) for (int j : adj[i]) aplink.insert(j); for (int i : {a.x, a.y, a.z}) aplink.erase(i); set<char>cols; for (int i : aplink) cols.insert(col[i]); for (char x = '1'; x <= '6'; x++) if (cols.count(x) == 0) { col[a.x] = x; col[a.y] = x; col[a.z] = x; } } for (int i = 0; i < 2 * n; i++) { for (int t = 0; t < (int)id[i].size(); t++) { cout << col[id[i][t]]; } cout << endl; } } else cout << "nemoguce\n"; }
#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...