Submission #119884

#TimeUsernameProblemLanguageResultExecution timeMemory
119884tutisTrapezi (COI17_trapezi)C++17
41 / 100
2 ms384 KiB
/*input 3 0000000 000000000 00000000000 00000000000 000000000 0000000 */ #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; bitset<54>x; bool ieskom(int i) { if (i >= 54) return true; if (x[i] == false) return ieskom(i + 1); for (int j = 0; j < (int)xx.size(); j++) { if (x[xx[j].x] && x[xx[j].y] && x[xx[j].z]) { if (xx[j].x == i || xx[j].y == i || xx[j].z == i) { x[xx[j].x] = false; x[xx[j].y] = false; x[xx[j].z] = false; xx[j].reikia = true; if (ieskom(i + 1)) return true; xx[j].reikia = false; x[xx[j].x] = true; x[xx[j].y] = true; x[xx[j].z] = true; } } } return false; } int kiek = 0; 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++); col.push_back(c); if (c == '0') kiek++; } vector<int>adj[timer]; 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 = 0; 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; xx.push_back(a); } } } } random_shuffle(xx.begin(), xx.end()); for (int i = 0; i < 2 * n; i++) { for (int t = 0; t < (int)id[i].size(); t++) { if (s[i][t] == '0') x[id[i][t]] = true; } } if (kiek % 3 == 0 && 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...