| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 589466 |
2022-07-04T18:34:06 Z |
Radewoosh |
Coins (LMIO19_monetos) |
C++14 |
|
724 ms |
262144 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];
unordered_map<int,pii> mapa[nax][nax];
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++)
mapa[i][j].clear();
mapa[0][n][0]={-inf, 0};
for (int i=0; i<=n; i++)
{
for (int j=n; j>=0; j--)
{
if (!active[i][j])
continue;
if (i)
{
for (auto l : mapa[i-1][j])
{
int x=l.first+j;
int y=l.second.first+kosz[i][j];
mini(mapa[i][j][x], {y, 0});
}
}
if (j<n)
{
for (auto l : mapa[i][j+1])
{
int x=l.first;
int y=l.second.first;
mini(mapa[i][j][x], {y, 1});
}
}
}
}
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 : mapa[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=mapa[x][y][v];
if (wez.second)
{
y++;
}
else
{
v-=y;
x--;
}
}
}
debug() << imie(mapa[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;
solve();
for (int h=5; h>=1; h--)
{
opti_to_active(h);
int wez=solve();
//~ debug() << h << " " << wez;
}
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:226:7: warning: unused variable 'wez' [-Wunused-variable]
226 | int wez=solve();
| ^~~
monetos.cpp:183:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d%d%d%d", &t, &n, &k1, &k2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:188:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
188 | scanf("%d", &tab[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
K = 17 |
| 2 |
Incorrect |
66 ms |
18608 KB |
K = 580 |
| 3 |
Runtime error |
724 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
707 ms |
262144 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
717 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
694 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
701 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
687 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
703 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
691 ms |
262144 KB |
Execution killed with signal 9 |
