Div.1 C and E are still under construction...
Tutorial is loading...
author's code:
#include<cstdio>
const int MAX_V = 201;
bool achieve[MAX_V];
void solve() {
int n, x;
scanf("%d%d", &n, &x);
for(int i = 1; i <= n + x; i++) {
achieve[i] = false;
}
for(int i = 1; i <= n; i++) {
int ranking;
scanf("%d", &ranking);
achieve[ranking] = true;
}
for(int k = n + x; k > 0; k--) {
int v = 0;
for(int i = 1; i <= k; i++) {
if(!achieve[i]) v++;
}
if(v <= x) {
printf("%d\n", k);
return;
}
}
}
int main() {
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
Tutorial is loading...
author's code:
#include<cstdio>
const int SIZE = 200000;
int p[SIZE];
int ans[SIZE][2];
int ans_cnt;
bool judge(int a[], int n){
static int used[SIZE+1];
for(int i = 1; i <= n; i++) used[i] = 0;
for(int i = 0; i < n; i++) used[a[i]] = 1;
for(int i = 1; i <= n; i++) {
if(!used[i]) return 0;
}
return 1;
}
bool judge(int len1, int n){
return judge(p, len1) && judge(p + len1, n - len1);
}
int main() {
int t = 0;
scanf("%d", &t);
while(t--) {
ans_cnt = 0;
int n;
scanf("%d", &n);
int ma=0;
for(int i = 0; i < n; i++) {
scanf("%d", &p[i]);
if(ma < p[i]) ma = p[i];
}
if(judge(n - ma,n)) {
ans[ans_cnt][0] = n - ma;
ans[ans_cnt++][1] = ma;
}
if(ma * 2 != n && judge(ma,n)) {
ans[ans_cnt][0] = ma;
ans[ans_cnt++][1] = n - ma;
}
printf("%d\n", ans_cnt);
for(int i = 0; i < ans_cnt; i++) {
printf("%d %d\n", ans[i][0], ans[i][1]);
}
}
return 0;
}
Tutorial is loading...
author's code:
#include<bits/stdc++.h>
const int SIZE = 100002;
int len[SIZE];
long long suffix_sum[SIZE];
void err() {puts("-1");}
void solve() {
int N, M;
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++) {
scanf("%d", &len[i]);
if(len[i] + i - 1 > N) {
err();
return;
}
}
for(int i = M; i > 0; i--) {
suffix_sum[i] = suffix_sum[i + 1] + len[i];
}
if(suffix_sum[1] < N) {
err();
return;
}
for(int i = 1; i <= M; i++) {
printf("%lld", std::max((long long)i, N - suffix_sum[i] + 1));
if(i < M) putchar(' ');
else puts("");
}
}
int main() {
solve();
return 0;
}
Tutorial is loading...
author's code:
#include<bits/stdc++.h>
void solve(){
int d, m;
scanf("%d%d",&d, &m);
long long answer=1;
for(int i = 0; i < 30; i++) {
if(d < (1 << i)) break;
answer = answer * (std::min((1 << (i+1)) - 1, d) - (1 << i) + 2) % m;
}
answer--;
if(answer < 0) answer += m;
printf("%lld\n",answer);
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
solve();
}
}
Tutorial is loading...
author's code (from bottom to top with min heap)
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1<<20;
int INF = 1000000001;
pair<int, int> a[SIZE];
int final_v[SIZE];
bool used[SIZE];
int h, g;
void pull(int id) {
while(a[id] > min(a[id<<1], a[(id<<1)|1])) {
if(a[id<<1] < a[(id << 1) | 1]) {
swap(a[id<<1], a[id]);
id <<= 1;
}
else {
swap(a[(id<<1)|1], a[id]);
id = (id << 1) | 1;
}
if(id >= (1 << h)) return;
}
}
void solve() {
scanf("%d%d", &h, &g);
long long an = 0;
for(int i = 1; i < (1 << h); i++) {
used[i] = 0;
scanf("%d", &a[i].first);
a[i].second = i;
final_v[i] = 0;
}
h--;
for(int lv = h - 1; lv >= 0; lv--) {
int ll = 1 << lv;
int rr = 1 << (lv + 1);
for(int i = ll; i < rr; i++) {
pair<int, int> tmp = a[i];
int bot = i << (h - lv);
a[i] = a[bot];
a[bot] = make_pair(INF, 0);
pull(i);
if(lv < g) {
int need_mi = max(final_v[i * 2], final_v[i * 2 + 1]);
while(a[i].first < need_mi) {
a[i] = make_pair(INF, 0);
pull(i);
}
an += final_v[i] = a[i].first;
used[a[i].second] = 1;
a[i] = tmp;
pull(i);
}
else {
a[bot] = tmp;
}
}
}
printf("%lld\n", an);
bool first_time = true;
for(int i = (1 << (h + 1)) - 1; i > 0; i--) {
if(!used[i]) {
if(!first_time) printf(" ");
else first_time = false;
printf("%d", i);
}
}
puts("");
}
int main(){
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
isaf27's code(from bottom to top with sorted array)
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 _y0
#define kill _kill
//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll btc = 30;
const ld eps = 1e-8;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(1e9 + 239);
const int MOD = 1e9 + 7; //
//random
mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());
//constants
const int M = (int)(2e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 20;
const int T = (1 << 20) + 239;
const int B = 500;
const int X = 35;
const int T2 = 2 * T;
int h, g, a[T2], n;
bool mark[T];
int id[T], buf[T], timer;
bool cmp(int i, int j)
{
return (a[i] < a[j]);
}
int pos;
void dfs_write(int p)
{
id[pos++] = p;
if (2 * p + 1 <= n)
{
dfs_write(2 * p);
dfs_write(2 * p + 1);
}
}
int dfs(int p, int sz)
{
if ((1 << (g - 1)) <= p && p < (1 << g))
{
int l = timer;
timer += sz;
pos = l;
dfs_write(p);
sort(id + l, id + l + sz, cmp);
mark[id[l]] = true;
return id[l];
}
int l = timer;
int new_sz = ((sz - 1) / 2);
int s1 = dfs(2 * p, new_sz);
int s2 = dfs(2 * p + 1, new_sz);
merge(id + l, id + l + new_sz, id + l + new_sz, id + l + new_sz + new_sz, buf, cmp);
buf[sz - 1] = p;
for (int i = 0; i < sz; i++)
id[i + l] = buf[i];
timer++;
if (cmp(s1, s2))
s1 = s2;
for (int i = 0; i < sz; i++)
if (cmp(s1, id[i + l]))
{
mark[id[i + l]] = true;
return id[i + l];
}
return 0;
}
void rm(int i)
{
if (a[2 * i] == 0 && a[2 * i + 1] == 0)
{
a[i] = 0;
mark[i] = false;
return;
}
if (a[2 * i] > a[2 * i + 1])
{
a[i] = a[2 * i];
mark[i] = mark[2 * i];
rm(2 * i);
}
else
{
a[i] = a[2 * i + 1];
mark[i] = mark[2 * i + 1];
rm(2 * i + 1);
}
}
void dfs_ans(int p)
{
while (a[p] != 0 && !mark[p])
{
cout << p << " ";
rm(p);
}
if (a[p] == 0)
return;
dfs_ans(2 * p);
dfs_ans(2 * p + 1);
}
void solve()
{
cin >> h >> g;
n = (1 << h) - 1;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
mark[i] = false;
timer = 0;
dfs(1, n);
ll ans = 0;
for (int i = 1; i <= n; i++)
if (mark[i])
ans += a[i];
cout << ans << "\n";
dfs_ans(1);
cout << "\n";
for (int i = 0; i <= n; i++)
a[i] = 0;
}
int32_t main()
{
#ifdef ONPC
freopen("input", "r", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
author's code (from top to bottom)
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1<<20;
int INF = 1000000001;
int a[SIZE], ops[SIZE];
int h, g;
int qq[24], qn;
int pull(int id) {
int tmp = a[id];
a[id] = 0;
qn = 0;
qq[qn++] = id;
while(id * 2 < (1 << h) && a[id] < max(a[id<<1], a[(id<<1)|1])) {
if(a[id<<1] > a[(id << 1) | 1]) {
swap(a[id<<1], a[id]);
id <<= 1;
}
else {
swap(a[(id<<1)|1], a[id]);
id = (id << 1) | 1;
}
qq[qn++] = id;
}
if(id < (1 << g)) {
for(int i = qn - 1; i > 0; i--) {
a[qq[i]] = a[qq[i - 1]];
}
a[qq[0]] = tmp;
return 0;
}
return tmp;
}
void solve() {
scanf("%d%d", &h, &g);
long long an = 0;
for(int i = 1; i < (1 << h); i++) {
scanf("%d", &a[i]);
an += a[i];
}
int need = 0;
for(int i = 1; i < (1 << g); i++) {
while(1) {
int v = pull(i);
if(v) {
an -= v;
ops[need++] = i;
}
else break;
}
}
printf("%lld\n", an);
for(int i = 0; i < need; i++) printf("%d%c", ops[i], " \n"[i == need - 1]);
}
int main(){
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
Tutorial is loading...
author's code:
#include<bits/stdc++.h>
using namespace std;
const int SIZE = 2e5+10;
char s[SIZE];
int cnt[SIZE];
int cc[26];
int all_cnt;
int ma;
void update_ma() {
while(ma > 0 && !cnt[ma]) ma--;
}
void dec1(int id) {
cnt[cc[id]]--;
cc[id]--;
cnt[cc[id]]++;
}
pair<int, int> stk[SIZE];
int sn;
int m;
int now;
int last_len;
void add(int i, bool flag) {
if(flag) {
dec1(stk[sn - 1].second);
dec1(stk[i].second);
all_cnt -= 2;
printf("%d %d\n",now + 1, now + stk[i].first);
update_ma();
sn--;
now -= stk[sn].first;
if(i + 1 < m) {
stk[i + 1].first += stk[sn].first;
}
else{
last_len += stk[sn].first;
}
}
else {
stk[sn++] = stk[i];
now += stk[i].first;
}
}
void solve(){
scanf("%s", s);
int n = strlen(s);
all_cnt = 0;
int lt = 0;
m = 0;
for(int i = 1; i < n; i++) {
if(s[i] == s[i - 1]) {
cc[s[i] - 'a']++;
all_cnt++;
stk[m++] = make_pair(i - lt, (int)(s[i] - 'a'));
lt = i;
}
}
last_len = n - lt;
ma = 0;
for(int i = 0; i < 26; i++) {
cnt[cc[i]]++;
ma = max(ma, cc[i]);
}
printf("%d\n", 1 + max(ma, (all_cnt + 1) / 2));
if(ma * 2 < all_cnt) {
sn = now = 0;
for(int i = 0; i < m; i++) {
add(i, sn && stk[sn - 1].second != stk[i].second && ma * 2 < all_cnt);
}
m = sn;
}
int main_id = -1;
for(int i = 0; i < 26; i++) {
if(cc[i] == ma) main_id = i;
}
sn = now = 0;
for(int i = 0; i < m; i++) {
add(i, sn && ((stk[sn - 1].second == main_id) ^ (stk[i].second == main_id)));
}
for(int i = 0; i < sn; i++) {
printf("%d %d\n",1 ,stk[i].first);
}
printf("%d %d\n", 1, last_len);
memset(cc, 0, sizeof(cc));
memset(cnt, 0, sizeof(int) * (ma + 1));
}
int main(){
int T;
scanf("%d", &T);
for(int i = 1; i <= T; i++) solve();
return 0;
}
Tutorial is loading...