| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 254162 |
2020-07-29T12:31:52 Z |
Berted |
Coins (LMIO19_monetos) |
C++14 |
|
672 ms |
231672 KB |
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <random>
#include <vector>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppp pair<pii, pii>
using namespace std;
const int INF = 1e9;
const int cst = 80;
int t, n, k1, k2, c;
int ar[351][351], pref[351][351], ans[351][351];
bool bt[351][351];
vector<ppp> v[90301];
vector<ppp> tp;
vector<int> tp2;
queue<pii> q;
int main()
{
mt19937 rng(6969420);
cin >> t >> n >> k1 >> k2;
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> ar[i][n - j + 1];
c += ar[i][n - j + 1];
}
for (int j = 1; j <= n; j++)
{
pref[i][j] = pref[i][j - 1] + ar[i][j];
}
}
for (int i = 0; i < n * (n + 1); i++)
{
v[i].reserve(2 * cst);
}
q.push({0, 0});
v[0].push_back({{c, 0}, {0, 0}});
while (q.size())
{
pii c = q.front(); q.pop();
//cout << "COORD : " << c.fst << ", " << c.snd << "\n";
sort(v[c.fst * (n + 1) + c.snd].begin(), v[c.fst * (n + 1) + c.snd].end());
for (auto x : v[c.fst * (n + 1) + c.snd])
{
while (tp.size() && tp.back().fst.fst == x.fst.fst) tp.pop_back();
while (tp.size() && tp.back().fst.snd <= x.fst.snd) tp.pop_back();
tp.push_back(x);
}
swap(v[c.fst * (n + 1) + c.snd], tp); tp.clear();
if (v[c.fst * (n + 1) + c.snd].size() > cst)
{
int k;
for (int i = 0; i < v[c.fst * (n + 1) + c.snd].size(); i++)
{
if (i & 1) tp2.push_back(i);
else tp.push_back(v[c.fst * (n + 1) + c.snd][i]);
}
k -= cst - (v[c.fst * (n + 1) + c.snd].size() + 1) / 2;
shuffle(tp2.begin(), tp2.end(), rng);
for (int i = 0; i < k; i++)
{
tp.push_back(v[c.fst * (n + 1) + c.snd][tp2[i]]);
}
tp2.clear();
swap(v[c.fst * (n + 1) + c.snd], tp); tp.clear();
}
/*
cout << "VECTOR :\n";
for (auto x : v[c.fst * (n + 1) + c.snd])
{
cout << x.fst.fst << ", " << x.fst.snd << " - " << x.snd.fst << ", " << x.snd.snd << "\n";
}
cout << "--\n";
*/
if (c.fst + 1 < n)
{
for (auto x : v[c.fst * (n + 1) + c.snd])
{
if (x.fst.fst >= c.snd)
{
v[(c.fst + 1) * (n + 1) + c.snd].push_back({{x.fst.fst - c.snd, x.fst.snd + pref[c.fst + 1][c.snd]}, {c.fst, c.snd}});
}
}
if (!bt[c.fst + 1][c.snd])
{
bt[c.fst + 1][c.snd] = 1;
q.push({c.fst + 1, c.snd});
}
}
if (c.snd + 1 <= n)
{
for (auto x : v[c.fst * (n + 1) + c.snd])
{
if (x.fst.fst)
{
v[c.fst * (n + 1) + c.snd + 1].push_back({{x.fst.fst - 1, x.fst.snd + ar[c.fst][c.snd + 1]}, {c.fst, c.snd}});
}
}
if (!bt[c.fst][c.snd + 1])
{
bt[c.fst][c.snd + 1] = 1;
q.push({c.fst, c.snd + 1});
}
}
}
int mx = -1, mx2; pii c;
//assert(::c - mx >= k1);
for (int i = 0; i <= n; i++)
{
for (auto x : v[(n - 1) * (n + 1) + i])
{
if (x.fst.snd > mx)
{
mx = x.fst.snd;
mx2 = x.fst.fst;
c = {n - 1, i};
}
}
}
//cout << mx << " " << mx2 << " " << c.fst << ", " << c.snd << "\n";
while (c != make_pair(0, 0))
{
//cout << "LOL : " << c.fst << ", " << c.snd << "\n";
for (auto x : v[c.fst * (n + 1) + c.snd])
{
if (x.fst == make_pair(mx2, mx))
{
if (x.snd == make_pair(c.fst - 1, c.snd))
{
mx = x.fst.snd - pref[c.fst][c.snd];
mx2 = x.fst.fst + c.snd;
for (int i = c.snd; i > 0; i--)
{
ans[c.fst][i] = 1;
::c--;
}
c = x.snd;
}
else
{
mx = x.fst.snd - ar[c.fst][c.snd];
mx2 = x.fst.fst + 1;
ans[c.fst][c.snd] = 1;
::c -= (c.snd > 0);
c = x.snd;
}
break;
}
}
}
/*
for (int i = 0; i < n; i++)
{
for (int j = n; j > 0; j--)
{
cout << ans[i][j];
if (j > 1) cout << " ";
}
cout << "\n";
}
cout << ::c << "\n";
*/
int pv = n;
for (int i = n - 1; i >= 0 && ::c; i--)
{
int cur = 0;
for (int j = 1; j <= pv && ::c; j++)
{
if (ans[i][j] == 1)
{
cur++;
}
else
{
ans[i][j] = 1; cur++; ::c--;
}
}
pv = cur;
}
// cout << ::c << "\n";
// assert(::c == 0);
for (int i = 0; i < n; i++)
{
for (int j = n; j > 0; j--)
{
cout << ans[i][j];
if (j > 1) cout << " ";
}
cout << "\n";
}
return 0;
}
Compilation message
monetos.cpp: In function 'int main()':
monetos.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[c.fst * (n + 1) + c.snd].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
monetos.cpp:72:6: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
k -= cst - (v[c.fst * (n + 1) + c.snd].size() + 1) / 2;
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
K = 17 |
| 2 |
Incorrect |
20 ms |
9080 KB |
K = 591 |
| 3 |
Partially correct |
643 ms |
231612 KB |
K = 20091 |
| 4 |
Partially correct |
661 ms |
231560 KB |
K = 22742 |
| 5 |
Partially correct |
672 ms |
231504 KB |
K = 17872 |
| 6 |
Partially correct |
655 ms |
231672 KB |
K = 21534 |
| 7 |
Partially correct |
650 ms |
231648 KB |
K = 22142 |
| 8 |
Partially correct |
651 ms |
231548 KB |
K = 20037 |
| 9 |
Partially correct |
648 ms |
231544 KB |
K = 21031 |
| 10 |
Partially correct |
645 ms |
231544 KB |
K = 21573 |
