976A - Минимальное двоичное число
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
if (n == 1) {
cout << s << endl;
} else {
int cnt0 = 0;
for (int i = 0; i < n; ++i)
cnt0 += s[i] == '0';
cout << 1;
for (int i = 0; i < cnt0; ++i)
cout << 0;
cout << endl;
}
return 0;
}
976B - Лара Крофт и новая игра
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m;
long long k;
int main() {
scanf("%d%d%lld", &n, &m, &k);
if (k < n){
printf("%lld 1\n", k + 1);
return 0;
}
k -= n;
long long row = k / (m - 1);
printf("%lld ", n - row);
if (row & 1)
printf("%lld\n", m - k % (m - 1));
else
printf("%lld\n", k % (m - 1) + 2);
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pt;
const int N = 300 * 1000 + 13;
int n;
pair<pt, int> a[N];
int main() {
scanf("%d", &n);
forn(i, n){
scanf("%d%d", &a[i].x.x, &a[i].x.y);
a[i].y = i + 1;
}
sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x) return a.x.x < b.x.x; return a.x.y > b.x.y;});
set<pt> cur;
forn(i, n){
while (!cur.empty() && cur.begin()->x < a[i].x.x)
cur.erase(cur.begin());
if (!cur.empty() && (--cur.end())->x >= a[i].x.y){
printf("%d %d\n", a[i].y, (--cur.end())->y);
return 0;
}
cur.insert({a[i].x.y, a[i].y});
}
puts("-1 -1");
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef pair<int, int> pt;
const int N = 100 * 1000 + 13;
int n;
vector<int> d;
vector<int> g[N];
vector<pt> construct(int st, vector<int> d){
if (d.empty())
return vector<pt>();
vector<pt> res;
forn(i, d[0])
for (int j = st + i + 1; j <= st + d.back(); ++j)
res.push_back({st + i, j});
int nxt = st + d[0];
for (int i = 1; i < int(d.size()); ++i)
d[i] -= d[0];
d.erase(d.begin());
if (!d.empty())
d.pop_back();
auto tmp = construct(nxt, d);
for (auto it : tmp)
res.push_back(it);
return res;
}
int main() {
scanf("%d", &n);
d.resize(n);
forn(i, n)
scanf("%d", &d[i]);
auto res = construct(0, d);
printf("%d\n", int(res.size()));
for (auto it : res)
printf("%d %d\n", it.first + 1, it.second + 1);
return 0;
}
Разбор
Tutorial is loading...
Решение (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 9;
int n, a, b;
int hp[N], dmg[N];
bool cmp(int i, int j){
if(hp[i] - dmg[i] != hp[j] - dmg[j])
return hp[i] - dmg[i] > hp[j] - dmg[j];
return i < j;
}
int get(int id){
return hp[id] > dmg[id]? hp[id] : dmg[id];
}
int main(){
scanf("%d %d %d", &n, &a, &b);
for(int i = 0; i < n; ++i)
scanf("%d %d", hp + i, dmg + i);
b = min(b, n);
vector <int> p(n);
for(int i = 0; i < n; ++i) p[i] = i;
sort(p.begin(), p.end(), cmp);
long long res = 0, sum = 0;
for(int i = 0; i < n; ++i){
int id = p[i];
if(i < b) sum += get(id);
else sum += dmg[id];
}
res = sum;
if(b == 0){
printf("%lld\n", res);
return 0;
}
long long x = (1LL << a);
for(int i = 0; i < n; ++i){
int id = p[i];
long long nres = sum;
if(i < b){
nres -= get(id);
nres += hp[id] * x;
res = max(res, nres);
}
else{
nres -= dmg[id];
nres += hp[id] * x;
int id2 = p[b - 1];
nres -= get(id2);
nres += dmg[id2];
res = max(res, nres);
}
}
printf("%lld\n", res);
return 0;
}
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
const int INF = int(1e9);
const int N = 4221;
struct edge {
int to, c, f, id;
edge(int to = 0, int c = 0, int f = 0, int id = -1) : to(to), c(c), f(f), id(id) {}
};
vector<edge> es;
vector<int> g[N];
void add_edge(int fr, int to, int cap, int id) {
g[fr].push_back(sz(es));
es.emplace_back(to, cap, 0, id);
g[to].push_back(sz(es));
es.emplace_back(fr, 0, 0, id);
}
int pw[N];
int n1, n2, m;
inline bool read() {
if(!(cin >> n1 >> n2 >> m))
return false;
fore(id, 0, m) {
int u, v;
assert(cin >> u >> v);
u--, v--;
pw[u]++;
pw[n1 + v]++;
add_edge(u, n1 + v, 1, id);
}
return true;
}
int d[N], q[N], hd, tl;
inline bool bfs(int s, int t, int n) {
fore(i, 0, n)
d[i] = INF;
hd = tl = 0;
d[s] = 0;
q[tl++] = s;
while(hd != tl) {
int v = q[hd++];
if(v == t)
break;
for(int id : g[v]) {
if(es[id].c - es[id].f == 0)
continue;
int to = es[id].to;
if(d[to] > d[v] + 1) {
d[to] = d[v] + 1;
q[tl++] = to;
}
}
}
return d[t] < INF;
}
int nxt[N];
int dfs(int v, int t, int mx) {
if(v == t) return mx;
if(mx == 0) return 0;
int sum = 0;
for(; nxt[v] < sz(g[v]); nxt[v]++) {
int id = g[v][nxt[v]];
int rem = es[id].c - es[id].f;
int to = es[id].to;
if(rem == 0 || d[to] != d[v] + 1)
continue;
int cur = 0;
if((cur = dfs(to, t, min(mx - sum, rem))) > 0) {
es[id].f += cur;
es[id ^ 1].f -= cur;
sum += cur;
}
if(sum == mx)
break;
}
return sum;
}
inline int dinic(int s, int t, int n) {
int mf = 0;
while(bfs(s, t, n)) {
fore(i, 0, n)
nxt[i] = 0;
int cf = 0;
while((cf = dfs(s, t, INF)) > 0)
mf += cf;
}
return mf;
}
vector<int> res[N];
inline void getCert(int k) {
fore(v, 0, n1) {
for(int id : g[v]) {
if(es[id].to < n1 || es[id].to >= n1 + n2)
continue;
assert(es[id].c > 0);
if(es[id].f > 0)
continue;
res[k].push_back(es[id].id);
}
}
}
void solve() {
int cnt = *min_element(pw, pw + n1 + n2);
int s = n1 + n2; int t = s + 1;
fore(i, 0, n1)
add_edge(s, i, pw[i] - cnt, -1);
fore(i, n1, n1 + n2)
add_edge(i, t, pw[i] - cnt, -1);
int mf = 0, mn = cnt;
while(mn >= 0) {
mf += dinic(s, t, n1 + n2 + 2);
getCert(mn);
if(mn > 0) {
for (int id : g[s]) {
assert(es[id].id < 0);
assert((id & 1) == 0);
es[id].c++;
}
for (int id : g[t]) {
assert(es[id].id < 0);
assert(es[id].c == 0);
es[id ^ 1].c++;
}
}
mn--;
}
fore(i, 0, cnt + 1) {
printf("%d ", sz(res[i]));
for(int id : res[i])
printf("%d ", id + 1);
puts("");
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
if(read()) {
solve();
}
return 0;
}
Исправьте пожалуйста описание разбора к B
An nlogn solution itself gave tle for me in C.nested segments question using c++ default sort function, is there any one like this.
http://codeforces.com/contest/976/submission/37770261
It is your cmpr function.
but exactly why it created problem??
it can't make rgt in increasing order
I am confused too.. what's the problem here? :/ I have submitted very much the same solution as yours and I have got Correct Answer!
http://codeforces.com/contest/976/submission/37790630
See this
Never use equal sign in compare function
you must use <,> operator with compare function,not <=,>=. because it can occur cycle in stl sorting.
When in doubt, read language specifications.
Here is the documentation for
sort. You can see that the 3rd argument needs to define a strict weak ordering. You can read about the mathematical concept, or you can go directly to the cpprefence of Compare.976D — Degree Set ,Graph for some (d1, d2, ..., dk) need to be sorted?
What do you mean by "sorted"? My checker takes the list of edges you output and calculates the degree set to compare it with the given one.
problem B
can You please explain why we don't consider the case, when we do -1 to k, by decreasing height of our final answer?
We transition from the number of steps Lara made to the number of cells she visited. You can see that she visits (m - 1) cells of the bottom row, then (m - 1) cells of the row above it and so on. And the formula tells you which one of these cells was the (k - n)-th.
Alternative solution for F: For a fixed degree d connect a new source vertex s with each vertex of U with capacity ∞ and demand d, and connect every vertex of V with capacity ∞ and demand d to a new sink vertex t. And then find the minimal flow as described in the e-maxx-eng article Flow with demands (add two more vertices to get rid of the demands, and do a binary search on the minimal flow value).
This has a worse complexity than the editorial solution (due to the binary search and a slightly bigger network), but my implementation 37840246 still runs in under 1 second using Edmond-Karp.
Is anyone getting WA on test case 10 of E well played :| http://codeforces.com/contest/976/submission/37842203 here is my submission
Same here: http://codeforces.com/contest/976/submission/37768647
I getted too, you are wrong because you are trying to maximize hp[i] * 2^a — dmg[i], but its not correct. For example you have got hp[i] * 2^a — dmg[i] > hp[j] * 2^a — dmg[j], but dmg[i] + hp[j] * 2^a — dmg[j] can be larger then dmg[j] + hp[i] * 2^a — dmg[i] and you should use your a spells on j but not i.
How is solution for E nlogn? If we precalc powers of two it is O(n) isnt it?
You need to sort your array complexity of sorting — nlogn.
Wow...wrote same solution after contest but now I forgot you need to sort hahaha
Changed >= to > om sort, and from Runtime error in test 84 got accepted.. Can someone explain why?
see this http://codeforces.com/blog/entry/59163?#comment-427659
Можно поподробнее разбор задачи D -- а то что-то вообще не понятно, откуда это все получается: "Граф для некоторого (d1, d2, ..., dk) можно получить из графа (d2 - d1, d3 - d1, ..., dk - 1 - d1) добавлением (dk - dk - 1) вершины, изначально не соединенной ни с чем, и d1 вершины, соединенной со всеми вершинами, объявленными ранее." Как "вершина, соединенная со всеми вершинами, объявленными ранее." может иметь степень d1, она будет иметь степень k — 1. И как "Вершины, не соединенные ни с чем, получат степень d1", если вершины не соединенные ни с чем имеют степень 0???
"Вершины, не соединенные ни с чем, получат степень d1", так как у нас есть d1 вершин которые соединены со всеми, значит вершины которые якобы ни с кем не соединены получат степень d1 ведь они соединены с теми вершинами.
Can you please add a link to this editorial that is accessible from the contest? I cannot access the editorial from here.
Done
Why is this wrong for question no. D?
Degree of vertex
5in your graph is1whereas the given degree set is{2, 3, 4}In problem F, why is the complexity O((n + m)2) ?
how to calculate dinic's complexity in problem F?why not n*n*m?
ME:making 100 of test cases for B problem codeforces: a single formula for all the cases ME: pikachu face INNER ME: crying
I do not understand the correctness of proof of problem D. How do we know that there is a solution for the sub-problem $$$(d_2 - d_1, d_3 - d_1, \cdots, d_{k - 1} - d_1)$$$. awoo Could you please help me with it?