| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1046977 | becaido | Wiring (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int L = 4;
const int R = 4;
ifstream in, in2;
ofstream out, out2;
const int N = 1200;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
int n, m, k;
double score, best;
string s[N], ans[N];
mt19937 rng(1919810);
int rnd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
bool is[N][N];
bool inside(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
bool valid(int x, int y) {
return inside(x, y) && s[x][y] == '.' && is[x][y] == 0;
}
int cnt[N][N], rnk[N][N];
set<tuple<int, int, int>> v;
void add(int x, int y) {
is[x][y] = 1;
if (v.count({rnk[x][y], x, y})) v.erase({rnk[x][y], x, y});
FOR (i, 0, 3) {
int tx = x + dx[i], ty = y + dy[i];
if (valid(tx, ty)) {
if (cnt[tx][ty] == 0) v.emplace(rnk[tx][ty], tx, ty);
else if (cnt[tx][ty] == 1) v.erase({rnk[tx][ty], tx, ty});
cnt[tx][ty]++;
}
}
}
void work(int sx, int sy) {
v.clear();
FOR (i, 1, n) FOR (j, 1, m) {
is[i][j] = cnt[i][j] = 0;
rnk[i][j] = rng();
}
add(sx, sy);
debug(sx, sy);
while (true) {
int mx = -1, ct = 0;
vector<pair<int, int>> cand, u;
for (auto [_, i, j] : v) if (s[i][j] == '.' && is[i][j] == 0 && cnt[i][j] == 1) {
int c = 1;
FOR (d, 0, 3) {
int tx = i + dx[d], ty = j + dy[d];
if (valid(tx, ty) && cnt[tx][ty] == 0) c++;
}
if (c > mx) {
mx = c;
cand.clear();
}
if (c == mx) cand.pb(i, j);
ct++;
// if (ct > 200) break;
}
if (mx == -1) break;
auto [x, y] = cand[rnd(0, cand.size() - 1)];
u.pb(x, y);
FOR (d, 0, 3) {
int tx = x + dx[d], ty = y + dy[d];
if (valid(tx, ty) && cnt[tx][ty] == 0) u.pb(tx, ty);
}
for (auto [x, y] : u) add(x, y);
}
int tot = 0;
FOR (i, 1, n) FOR (j, 1, m) if (is[i][j]) {
int c = 0;
FOR (d, 0, 3) {
int tx = i + dx[d], ty = j + dy[d];
if (inside(tx, ty) && is[tx][ty]) c++;
}
if (c == 1) tot++;
}
double cur = (double) 10 * tot / k;
if (cur > best) {
FOR (i, 1, n) {
ans[i] = s[i];
FOR (j, 1, m) if (s[i][j] == '.' && is[i][j] == 0) ans[i][j] = 'X';
}
best = cur;
}
}
void solve(int Case) {
in >> n >> m >> k;
score = best = 0;
in2 >> score;
vector<pair<int, int>> all;
FOR (i, 1, n) {
in >> s[i];
s[i] = " " + s[i];
FOR (j, 1, m) if (s[i][j] == '.') all.pb(i, j);
}
double st = clock();
shuffle(all.begin(), all.end(), rng);
// all.resize(10);
for (auto [x, y] : all) {
work(x, y);
if ((clock() - st) / CLOCKS_PER_SEC >= 30) break;
}
if (best > score) {
score = best;
out.close(), out2.close();
out.open("nowruz" + to_string(Case) + ".out.txt");
out2.open("history" + to_string(Case) + ".txt");
FOR (i, 1, n) out << ans[i].substr(1) << '\n';
out2 << fixed << setprecision(8) << score << '\n';
debug(Case, best);
}
}
int main() {
FOR (i, L, R) {
debug(i);
in.close(), in2.close();
in.open("anowruz" + to_string(i) + ".in.txt");
in2.open("history" + to_string(i) + ".txt");
solve(i);
}
}