Div.1 C and E are still under construction...↵
↵
[tutorial:1330A]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1330B]↵
↵
author's code:↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1329A]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1329B]↵
↵
<spoiler summary="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();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1329C]↵
↵
↵
<spoiler summary="author's code:↵
">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1329D]↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1329E]↵
↵
[tutorial:1330A]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1330B]↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1329A]↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1329B]↵
↵
<spoiler summary="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();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1329C]↵
↵
↵
<spoiler summary="author's code:
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1329D]↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1329E]↵
