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;
}