| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 589497 |
2022-07-04T19:13:54 Z |
Radewoosh |
Coins (LMIO19_monetos) |
C++14 |
|
923 ms |
212300 KB |
//~ 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;
const int inf=1e9;
int t, k1, k2;
int n;
int tab[nax][nax];
int kosz[nax][nax];
int zera;
int active[nax][nax];
int wz[nax][nax];
int opti[nax][nax];
vector<pair<int,pii>> dp[nax][nax];
int wazne[nax*nax];
pii tso[nax*nax];
vi lis;
void mini(pii &a, pii b)
{
a=min(a, b);
}
int solve()
{
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
dp[i][j]={};
dp[0][n].push_back({0, {-inf, 0}});
for (int i=0; i<=n; i++)
{
for (int j=n; j>=0; j--)
{
if (!active[i][j])
continue;
if (i==0 && j==n)
continue;
lis.clear();
if (i)
{
for (auto l : dp[i-1][j])
{
int x=l.first+j;
int y=l.second.first+kosz[i][j];
if (!wazne[x])
{
wazne[x]=1;
tso[x]={inf, 0};
lis.push_back(x);
}
mini(tso[x], {y, 0});
}
}
if (j<n)
{
for (auto l : dp[i][j+1])
{
int x=l.first;
int y=l.second.first;
if (!wazne[x])
{
wazne[x]=1;
tso[x]={inf, 0};
lis.push_back(x);
}
mini(tso[x], {y, 1});
}
}
dp[i][j].resize(lis.size());
int id=0;
for (int l : lis)
{
wazne[l]=0;
dp[i][j][id++]={l, tso[l]};
}
}
}
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
opti[i][j]=0;
pii a{inf, 0};
pii b{inf, 0};
for (auto i : dp[n][0])
{
if (i.first<=zera)
a=min(a, {zera-i.first, i.second.first});
if (i.first>=zera)
b=min(b, {i.first-zera, i.second.first});
}
opti[0][n]=1;
for (int h : {zera-a.first, zera+b.first})
{
if (abs(h)>inf/2)
{
debug() << "skip";
continue;
}
int x=n;
int y=0;
int v=h;
while(x>0 || y<n)
{
opti[x][y]=1;
pii wez;
for (auto i : dp[x][y])
if (i.first==v)
wez=i.second;
if (wez.second)
{
y++;
}
else
{
v-=y;
x--;
}
}
}
debug() << imie(dp[n][0].size());
if (a.first)
return -1;
return a.second;
}
int rx[]={-1, 1, 0, 0};
int ry[]={0, 0, -1, 1};
void relax(int a, int b)
{
for (int i=0; i<4; i++)
{
int x=a+rx[i];
int y=b+ry[i];
if (x>=0 && y>=0)
active[a][b]=max(active[a][b], active[x][y]-1);
}
}
void opti_to_active(int v)
{
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
active[i][j]=(opti[i][j]*v);
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
relax(i, j);
for (int i=n; i>=0; i--)
for (int j=n; j>=0; j--)
relax(i, j);
}
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=1; i<=n; i++)
{
int x=0;
for (int j=1; j<=n; j++)
if (!tab[i][j])
x++;
kosz[i][0]=x;
for (int j=1; j<=n; j++)
{
x-=(tab[i][j]==0);
x+=(tab[i][j]==1);
kosz[i][j]=x;
}
}
set<int> px, py;
for (int h=0; h<2; h++)
{
py=px;
px.clear();
const int d=25;
for (int j=0; j<=d; j++)
px.insert(n*j/d);
}
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
active[i][j]=0;
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
if (px.count(i) || py.count(j))
active[i][j]=1;
int ost=solve();
for (int h=1; h<=1+5*(n>50); h++)
{
opti_to_active(5+2*(ost>-1)+(n<=50)*10);
ost=solve();
}
for (int i=1; i<=n; i++)
{
int x=0;
for (int j=n; j; j--)
{
if (opti[i][j])
x=1;
wz[i][j]=x;
}
}
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:212:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | scanf("%d%d%d%d", &t, &n, &k1, &k2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:217:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | scanf("%d", &tab[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2516 KB |
K = 17 |
| 2 |
Correct |
26 ms |
16568 KB |
K = 576 |
| 3 |
Correct |
819 ms |
167884 KB |
K = 18598 |
| 4 |
Correct |
720 ms |
165376 KB |
K = 21795 |
| 5 |
Correct |
727 ms |
161388 KB |
K = 17073 |
| 6 |
Correct |
923 ms |
212300 KB |
K = 20816 |
| 7 |
Correct |
845 ms |
173328 KB |
K = 21454 |
| 8 |
Correct |
796 ms |
150204 KB |
K = 19587 |
| 9 |
Correct |
769 ms |
165516 KB |
K = 20736 |
| 10 |
Correct |
758 ms |
165940 KB |
K = 20131 |
