Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Codeforces Round #631 Editorial

Revision en3, by dreamoon_love_AA, 2020-04-03 21:42:38

Div.1 C and E is still under construction...

author's code: ~~~~~

# include

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; } ~~~~~

author's code: ~~~~~

# include

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; } ~~~~~

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; } ~~~~~

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(); } } ~~~~~

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; } ~~~~~

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; } ~~~~~

#### History

Revisions

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