Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
x, k = map(int, input().split())
if x % k != 0:
print(1)
print(x)
else:
print(2)
print(1, x - 1)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
string s;
cin >> s;
int ans = 1, cur = 1;
for(int i = 1; i < n; i++)
{
if(s[i] != s[i - 1]) cur = 1;
else cur++;
ans = max(ans, cur);
}
cout << ans + 1 << endl;
}
}
1837C - Лучшая двоичная строка
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
char x = '0';
for (auto& c : s) {
if (c == '?') c = x;
x = c;
}
cout << s << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
string s;
cin >> s;
vector<int> bal(n + 1);
for(int j = 0; j < n; j++)
if(s[j] == '(')
bal[j + 1] = bal[j] + 1;
else
bal[j + 1] = bal[j] - 1;
if(bal.back() != 0)
cout << -1 << endl;
else
{
if(*min_element(bal.begin(), bal.end()) == 0 || *max_element(bal.begin(), bal.end()) == 0)
{
cout << 1 << endl;
for(int j = 0; j < n; j++)
{
if(j) cout << " ";
cout << 1;
}
cout << endl;
}
else
{
cout << 2 << endl;
vector<int> ans;
int cur = 0;
while(cur < n)
{
int w = (s[cur] == '(' ? 1 : 2);
do
{
cur++;
ans.push_back(w);
}
while(bal[cur] != 0);
}
for(int j = 0; j < n; j++)
{
if(j) cout << " ";
cout << ans[j];
}
cout << endl;
}
}
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int main() {
int k;
scanf("%d", &k);
vector<int> a(1 << k);
forn(i, 1 << k){
scanf("%d", &a[i]);
if (a[i] != -1) --a[i];
}
int ans = 1;
for (int st = k - 1; st >= 0; --st){
int big = 1 << st, fr = 0;
vector<int> na(1 << st);
forn(i, 1 << st){
int mn = min(a[2 * i], a[2 * i + 1]);
int mx = max(a[2 * i], a[2 * i + 1]);
if (mn == -1){
if (mx >= (1 << st)){
--big;
na[i] = -1;
}
else if (mx != -1){
na[i] = mx;
}
else{
na[i] = -1;
++fr;
}
continue;
}
if ((a[2 * i] < (1 << st)) == (a[2 * i + 1] < (1 << st))){
puts("0");
return 0;
}
na[i] = mn;
--big;
}
forn(_, fr) ans = ans * 2ll % MOD;
for (int i = 1; i <= big; ++i) ans = ans * 1ll * i % MOD;
a = na;
}
printf("%d\n", ans);
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<int> pr(n + 1), su(n + 1);
auto check = [&](long long x){
forn(_, 2){
priority_queue<int> cur;
pr[0] = 0;
long long cursum = 0;
forn(i, n){
cur.push(a[i]);
cursum += a[i];
while (cursum > x){
cursum -= cur.top();
cur.pop();
}
pr[i + 1] = cur.size();
}
reverse(a.begin(), a.end());
swap(pr, su);
}
reverse(su.begin(), su.end());
forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
return false;
};
long long l = 1, r = accumulate(a.begin(), a.end(), 0ll);
long long res = 0;
while (l <= r){
long long m = (l + r) / 2;
if (check(m)){
res = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%lld\n", res);
}
}
Решение 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<pair<int, int>> xs(n);
forn(i, n) xs[i] = {a[i], i};
sort(xs.begin(), xs.end());
forn(i, n) a[i] = lower_bound(xs.begin(), xs.end(), make_pair(a[i], i)) - xs.begin();
vector<int> lstpr(n), lstsu(n);
forn(_, 2){
set<int> cur;
forn(i, n){
auto it = cur.insert(a[i]).first;
if (it == cur.begin())
lstpr[i] = n;
else
lstpr[i] = *(--it);
}
swap(lstpr, lstsu);
reverse(a.begin(), a.end());
}
vector<int> pr(n + 1), su(n + 1);
vector<int> prv(n + 2), nxt(n + 2);
auto check = [&](long long x){
forn(_, 2){
int cnt = 0;
prv[n + 1] = n;
nxt[n] = n + 1;
pr[0] = 0;
int mn = 1e9;
long long cursum = 0;
forn(i, n){
if (mn < a[i]){
pr[i + 1] = cnt;
continue;
}
nxt[a[i]] = nxt[lstpr[i]];
prv[nxt[a[i]]] = a[i];
prv[a[i]] = lstpr[i];
nxt[prv[a[i]]] = a[i];
cursum += xs[a[i]].first;
++cnt;
while (cursum > x){
mn = min(mn, prv[n + 1]);
cursum -= xs[prv[n + 1]].first;
prv[n + 1] = prv[prv[n + 1]];
nxt[prv[n + 1]] = n + 1;
--cnt;
}
pr[i + 1] = cnt;
}
reverse(a.begin(), a.end());
swap(lstpr, lstsu);
swap(pr, su);
}
reverse(su.begin(), su.end());
forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
return false;
};
long long l = 1, r = 0;
for (int x : a) r += xs[x].first;
long long res = 0;
while (l <= r){
long long m = (l + r) / 2;
if (check(m)){
res = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%lld\n", res);
}
}