Codeforces Round #631 Editorial
Difference between en5 and en6, changed 238 character(s)
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 &mdash; 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 &mdash; ma,n)) {↵
            ans[ans_cnt][0] = n &mdash; ma;↵
            ans[ans_cnt++][1] = ma;↵
        }↵
        if(ma * 2 != n && judge(ma,n)) {↵
            ans[ans_cnt][0] = ma;↵
            ans[ans_cnt++][1] = n &mdash; 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 &mdash; 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 &mdash; 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)) &mdash; 1, d) &mdash; (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 &mdash; 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 &mdash; 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)) &mdash; 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 &mdash; 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 &mdash; 1]) {↵
            cc[s[i] &mdash; 'a']++;↵
            all_cnt++;↵
            stk[m++] = make_pair(i &mdash; lt, (int)(s[i] &mdash; 'a'));↵
            lt = i;↵
        }↵
    }↵
    last_len = n &mdash; 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 &mdash; 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 &mdash; 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]↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en21 English dreamoon_love_AA 2020-04-05 21:15:08 1 Tiny change: '5] provide proof for' -> '5] provides proof for'
en20 English dreamoon_love_AA 2020-04-05 21:14:23 143
en19 English dreamoon_love_AA 2020-04-05 20:31:48 53 Tiny change: '#### **Div.1 E is still under construction...**\n\n[tutorial:' -> '[tutorial:'
en18 English dreamoon_love_AA 2020-04-05 17:13:21 8807
en17 English dreamoon_love_AA 2020-04-05 07:59:53 159 Tiny change: 'takk].\n\n<spoil' -> 'takk].\n\n\n\n<spoil'
en16 English dreamoon_love_AA 2020-04-05 01:12:06 2 Tiny change: '# **Div.1 C E is stil' -> '# **Div.1 E is stil'
en15 English dreamoon_love_AA 2020-04-05 00:46:24 13
en14 English dreamoon_love_AA 2020-04-04 22:23:28 1518
en13 English dreamoon_love_AA 2020-04-04 22:16:37 3500
en12 English dreamoon_love_AA 2020-04-04 00:10:34 4
en11 English dreamoon_love_AA 2020-04-04 00:09:37 9 (published)
en10 English dreamoon_love_AA 2020-04-04 00:05:13 20 Tiny change: 'oiler>\n\n' -> 'oiler>\n\n\n[tutorial:1329E]\n'
en9 English dreamoon_love_AA 2020-04-04 00:04:54 18 Tiny change: 'oiler>\n\n[tutorial:1329E]\n' -> 'oiler>\n\n' (saved to drafts)
en8 English dreamoon_love_AA 2020-04-03 22:16:10 144
en7 English dreamoon_love_AA 2020-04-03 22:13:29 8 Tiny change: 'long)i, N &mdash; suffix_su' -> 'long)i, N - suffix_su'
en6 English dreamoon_love_AA 2020-04-03 21:56:32 238
en5 English dreamoon_love_AA 2020-04-03 21:44:17 5 Tiny change: '1 C and E is still und' -> '1 C and E are still und' (published)
en4 English dreamoon_love_AA 2020-04-03 21:43:34 12
en3 English dreamoon_love_AA 2020-04-03 21:42:38 7309
en2 English dreamoon_love_AA 2020-04-03 21:35:25 156
en1 English dreamoon_love_AA 2020-04-03 21:34:20 307 Initial revision (saved to drafts)