Submission #119828

#TimeUsernameProblemLanguageResultExecution timeMemory
119828tutisTrapezi (COI17_trapezi)C++17
6 / 100
452 ms512 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]; clock_t pradzia; void ieskom() { if ((clock() - pradzia) * 100 >= 45 * CLOCKS_PER_SEC || kiek == 0) return; int i = rand() % xx.size(); if (xx[i].reikia && (rand() % 2 == 0)) { kiek += 3; xx[i].reikia = false; } else if (xx[i].reikia == false) { bool ok = true; for (grupe j : xx) { if (j.reikia) { ok &= (xx[i].x != j.x); ok &= (xx[i].x != j.y); ok &= (xx[i].x != j.z); ok &= (xx[i].y != j.x); ok &= (xx[i].y != j.y); ok &= (xx[i].y != j.z); ok &= (xx[i].z != j.x); ok &= (xx[i].z != j.y); ok &= (xx[i].z != j.z); } } if (ok) { kiek -= 3; xx[i].reikia = true; } } ieskom(); } int main() { pradzia = clock(); ios_base::sync_with_stdio(false); 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++; } 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] == '0' && col[a.y] == '0' && col[a.z] == '0') xx.push_back(a); } } } } ieskom(); if (kiek == 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...