Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// int tt = clock();
#endif
int T; cin >> T;
while(T--) {
int n, d;
cin >> n >> d;
int x, MAG = (int)sqrt(d) + 10;
for(x = 0; x < MAG; x++) {
if(x + (d + x) / (x + 1) <= n)
break;
}
cout << (x < MAG ? "YES" : "NO") << endl;
}
return 0;
}
1288B - Очередная мемная задача
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
for t in range(int(input())):
a, b = map(int, input().split())
print(a * (len(str(b + 1)) - 1))
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Roms)
from math import factorial as fact
mod = 10**9 + 7
def C(n, k):
return fact(n) // (fact(k) * fact(n - k))
n, m = map(int, input().split())
print(C(n + 2*m - 1, 2*m) % mod)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int> > a;
int a1, a2;
bool can(int mid)
{
vector<int> msk(1 << m, -1);
for(int i = 0; i < n; i++)
{
int cur = 0;
for(int j = 0; j < m; j++)
if(a[i][j] >= mid)
cur ^= (1 << j);
msk[cur] = i;
}
if(msk[(1 << m) - 1] != -1)
{
a1 = a2 = msk[(1 << m) - 1];
return true;
}
for(int i = 0; i < (1 << m); i++)
for(int j = 0; j < (1 << m); j++)
if(msk[i] != -1 && msk[j] != -1 && (i | j) == (1 << m) - 1)
{
a1 = msk[i];
a2 = msk[j];
return true;
}
return false;
}
int main()
{
scanf("%d %d", &n, &m);
a.resize(n, vector<int>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
int lf = 0;
int rg = int(1e9) + 43;
while(rg - lf > 1)
{
int m = (lf + rg) / 2;
if(can(m))
lf = m;
else
rg = m;
}
assert(can(lf));
printf("%d %d\n", a1 + 1, a2 + 1);
}
Идея: Neon
Разбор
Tutorial is loading...
Решение 1 (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;
const int N = 300 * 1000 + 13;
const int P = 550;
typedef pair<int, int> pt;
int n;
int a[N];
vector<int> pos[N];
pt ans[N];
int cnt[N];
int tot;
void add(int x){
++cnt[x];
if (cnt[x] == 1) ++tot;
}
void rem(int x){
if (cnt[x] == 1) --tot;
--cnt[x];
}
int f[N];
void upd(int x){
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
++f[i];
}
int get(int x){
int res = 0;
for (int i = x; i < N; i |= i + 1)
res += f[i];
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
}
forn(i, m){
pos[a[i]].push_back(i);
}
vector<pt> qr;
forn(i, n){
for (int j = 1; j < int(pos[i].size()); ++j)
qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
if (!pos[i].empty())
qr.push_back(make_pair(pos[i].back() + 1, m - 1));
}
sort(qr.begin(), qr.end(), [](const pt &a, const pt &b){
if (a.x / P != b.x / P)
return a.x < b.x;
if ((a.x / P) & 1)
return a.y < b.y;
return a.y > b.y;
});
forn(i, n) ans[i] = {i, i};
forn(i, m) ans[a[i]].x = 0;
int L = 0, R = -1;
forn(i, qr.size()){
int l = qr[i].x;
int r = qr[i].y;
if (r < l) continue;
int x = a[qr[i].x - 1];
while (L < l) rem(a[L++]);
while (L > l) add(a[--L]);
while (R > r) rem(a[R--]);
while (R < r) add(a[++R]);
ans[x].y = max(ans[x].y, tot);
}
forn(i, m){
if (i == pos[a[i]][0]){
ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
upd(a[i]);
}
}
forn(i, n) if (pos[i].empty()){
ans[i].y = max(ans[i].y, i + get(i));
}
forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
return 0;
}
Решение 2 (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;
const int N = 300 * 1000 + 13;
typedef pair<int, int> pt;
int n;
int a[N];
vector<int> pos[N];
pt ans[N];
int prv[N];
vector<int> t[4 * N];
void build(int v, int l, int r){
if (l == r - 1){
t[v].push_back(prv[l]);
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v].resize(r - l);
merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin());
}
int get(int v, int l, int r, int L, int R, int val){
if (L >= R)
return 0;
if (l == L && r == R)
return lower_bound(t[v].begin(), t[v].end(), val) - t[v].begin();
int m = (l + r) / 2;
return get(v * 2, l, m, L, min(m, R), val) + get(v * 2 + 1, m, r, max(m, L), R, val);
}
int f[N];
void upd(int x){
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
++f[i];
}
int get(int x){
int res = 0;
for (int i = x; i < N; i |= i + 1)
res += f[i];
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
}
forn(i, m){
pos[a[i]].push_back(i);
}
vector<pt> qr;
forn(i, n){
for (int j = 1; j < int(pos[i].size()); ++j)
qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
if (!pos[i].empty())
qr.push_back(make_pair(pos[i].back() + 1, m - 1));
}
forn(i, n) ans[i] = {i, i};
forn(i, m) ans[a[i]].x = 0;
forn(i, n){
int cur = -1;
for (auto it : pos[i]){
prv[it] = cur;
cur = it;
}
}
build(1, 0, m);
forn(i, qr.size()){
int l = qr[i].x;
int r = qr[i].y;
if (r < l) continue;
int x = a[qr[i].x - 1];
int cnt = get(1, 0, m, l, r + 1, l);
ans[x].y = max(ans[x].y, cnt);
}
forn(i, m){
if (i == pos[a[i]][0]){
ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
upd(a[i]);
}
}
forn(i, n) if (pos[i].empty()){
ans[i].y = max(ans[i].y, i + get(i));
}
forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
return 0;
}
Решение 3 (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 600 * 1000 + 13;
int f[N];
void upd(int x, int val){
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
f[i] += val;
}
int get(int x){
int res = 0;
for (int i = x; i < N; i |= i + 1)
res += f[i];
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> mn(n);
iota(mn.begin(), mn.end(), 0);
vector<int> mx = mn;
vector<int> a(m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
mn[a[i]] = 0;
}
vector<int> pos(n);
forn(i, n) pos[i] = n - i - 1;
forn(i, n) upd(i, 1);
forn(i, m){
mx[a[i]] = max(mx[a[i]], get(pos[a[i]] + 1));
upd(pos[a[i]], -1);
pos[a[i]] = i + n;
upd(pos[a[i]], 1);
}
forn(i, n){
mx[i] = max(mx[i], get(pos[i] + 1));
}
forn(i, n) printf("%d %d\n", mn[i] + 1, mx[i] + 1);
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 443;
int n1, n2, m, r, b;
string s1, s2;
int u[N];
int v[N];
struct edge
{
int y, c, f, cost;
edge() {};
edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};
int bal[N][N];
int s, t, oldS, oldT, V;
vector<int> g[N];
vector<edge> e;
void add(int x, int y, int c, int cost)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, 0, cost));
g[y].push_back(e.size());
e.push_back(edge(x, 0, 0, -cost));
}
int rem(int num)
{
return e[num].c - e[num].f;
}
void add_LR(int x, int y, int l, int r, int cost)
{
int c = r - l;
if(l > 0)
{
add(s, y, l, cost);
add(x, t, l, cost);
}
if(c > 0)
{
add(x, y, c, cost);
}
}
int p[N];
int d[N];
int pe[N];
int inq[N];
bool enlarge()
{
for(int i = 0; i < V; i++)
{
d[i] = int(1e9);
p[i] = -1;
pe[i] = -1;
inq[i] = 0;
}
d[s] = 0;
queue<int> q;
q.push(s);
inq[s] = 1;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = 0;
for(auto z : g[k])
{
if(!rem(z)) continue;
if(d[e[z].y] > d[k] + e[z].cost)
{
p[e[z].y] = k;
pe[e[z].y] = z;
d[e[z].y] = d[k] + e[z].cost;
if(!inq[e[z].y])
{
q.push(e[z].y);
inq[e[z].y] = 1;
}
}
}
}
if(p[t] == -1)
return false;
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
return true;
}
void add_edge(int x, int y)
{
add(x, y + n1, 1, r);
add(y + n1, x, 1, b);
}
void impose_left(int x)
{
if(s1[x] == 'R')
{
add_LR(oldS, x, 1, m, 0);
}
else if(s1[x] == 'B')
{
add_LR(x, oldT, 1, m, 0);
}
else
{
add(oldS, x, m, 0);
add(x, oldT, m, 0);
}
}
void impose_right(int x)
{
if(s2[x] == 'R')
{
add_LR(x + n1, oldT, 1, m, 0);
}
else if(s2[x] == 'B')
{
add_LR(oldS, x + n1, 1, m, 0);
}
else
{
add(oldS, x + n1, m, 0);
add(x + n1, oldT, m, 0);
}
}
void construct_bal()
{
for(int i = 0; i < n1; i++)
{
for(auto z : g[i])
{
if(e[z].y >= n1 && e[z].y < n1 + n2)
bal[i][e[z].y - n1] += e[z].f;
}
}
}
void find_ans()
{
int res = 0;
string w = "";
for(auto x : g[s])
if(rem(x))
{
cout << -1 << endl;
return;
}
for(int i = 0; i < m; i++)
{
if(bal[u[i]][v[i]] > 0)
{
bal[u[i]][v[i]]--;
res += r;
w += "R";
}
else if(bal[u[i]][v[i]] < 0)
{
bal[u[i]][v[i]]++;
res += b;
w += "B";
}
else w += "U";
}
cout << res << endl << w << endl;
}
int main()
{
cin >> n1 >> n2 >> m >> r >> b;
cin >> s1;
cin >> s2;
for(int i = 0; i < m; i++)
{
cin >> u[i] >> v[i];
u[i]--;
v[i]--;
}
oldS = n1 + n2;
oldT = oldS + 1;
s = oldT + 1;
t = s + 1;
V = t + 1;
for(int i = 0; i < n1; i++)
impose_left(i);
for(int i = 0; i < n2; i++)
impose_right(i);
for(int i = 0; i < m; i++)
add_edge(u[i], v[i]);
add(oldT, oldS, 100000, 0);
while(enlarge());
construct_bal();
find_ans();
}