//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define shandom_ruffle random_shuffle
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=307;
int t, k1, k2;
int n;
int tab[nax][nax];
int zera;
int wz[nax][nax];
int wyn;
vector<pii> n1, n0;
void cons(int a, int b)
{
if (a<1 || b<1 || a>n || b>n)
return;
if (!wz[a][b] && wz[a-1][b] && wz[a][b-1])
n1.push_back({a, b});
if (wz[a][b] && !wz[a+1][b] && !wz[a][b+1])
n0.push_back({a, b});
}
int main()
{
scanf("%d%d%d%d", &t, &n, &k1, &k2);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
scanf("%d", &tab[i][j]);
zera+=!tab[i][j];
}
}
for (int i=0; i<=n; i++)
wz[i][0]=wz[0][i]=1;
vector<pii> kol;
kol.push_back({1, 1});
for (int h=1; h<=zera; h++)
{
swap(kol[rand()%kol.size()], kol.back());
pii v=kol.back();
kol.pop_back();
wz[v.first][v.second]=1;
if (v.first<n && wz[v.first+1][v.second-1])
kol.push_back({v.first+1, v.second});
if (v.second<n && wz[v.first-1][v.second+1])
kol.push_back({v.first, v.second+1});
}
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
wyn+=(tab[i][j]==wz[i][j]);
n1=kol;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if (wz[i][j] && !wz[i+1][j] && !wz[i][j+1])
n0.push_back({i, j});
while(wyn/2>k1)
{
//~ debug() << imie(wyn) << " " << n0.size() << " " << n1.size();
//~ for (int i=1; i<=n; i++)
//~ debug() << range(wz[i]+1, wz[i]+1+n);
//~ static int li=3000;
//~ li--;
//~ if (!li)
//~ return 0;
swap(n0[rand()%n0.size()], n0.back());
swap(n1[rand()%n1.size()], n1.back());
pii zero=n0.back();
pii jede=n1.back();
if (wz[jede.first][jede.second] || !wz[jede.first-1][jede.second] || !wz[jede.first][jede.second-1])
{
n1.pop_back();
continue;
}
if (!wz[zero.first][zero.second] || wz[zero.first+1][zero.second] || wz[zero.first][zero.second+1])
{
n0.pop_back();
continue;
}
if (jede.first>=zero.first && jede.second>=zero.second)
continue;
int nowy=wyn-(tab[jede.first][jede.second]==0)-(tab[zero.first][zero.second]==1)+(tab[jede.first][jede.second]==1)+(tab[zero.first][zero.second]==0);
//~ if (nowy>wyn)
if (nowy>wyn && (rand()%100))
continue;
wyn=nowy;
n0.pop_back();
n1.pop_back();
wz[jede.first][jede.second]=1;
wz[zero.first][zero.second]=0;
cons(jede.first, jede.second);
cons(jede.first+1, jede.second);
cons(jede.first, jede.second+1);
cons(zero.first, zero.second);
cons(zero.first-1, zero.second);
cons(zero.first, zero.second-1);
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
printf("%d ", wz[i][j]^1);
printf("\n");
}
return 0;
}
Compilation message
monetos.cpp: In function 'int main()':
monetos.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d%d%d%d", &t, &n, &k1, &k2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d", &tab[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
K = 17 |
| 2 |
Correct |
172 ms |
340 KB |
K = 576 |
| 3 |
Execution timed out |
2081 ms |
980 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2083 ms |
980 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2086 ms |
980 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2087 ms |
980 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2083 ms |
904 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2045 ms |
1028 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2071 ms |
980 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2080 ms |
980 KB |
Time limit exceeded |
