| Endagorion CF Rounds |
| 1 | int main() { ios::sync_with_stdio(false); cout.precision(10); cout << fixed; int N, K; cin >> N >> K; int l = 1, r = K + 1; forn(i, K + 1) { if (i % 2 == 0) cout << l++ << ' '; else cout << r-- << ' '; } for (int j = K + 2; j <= N; ++j) cout << j << ' '; cout << ' '; return 0; } |
| 2 | int p[30][100001]; int d[30][100001]; struct TEvent { int l, r, q; TEvent(int l = 0, int r = 0, int q = 0) : l(l) , r(r) , q(q) { } }; vector<TEvent> evs[30]; int main() { ios::sync_with_stdio(false); cout.precision(10); cout << fixed; int N, M; cin >> N >> M; forn(i, M){ int l, r, q; cin >> l >> r >> q; --l; forn(j, 30) { int x = (q >> j) & 1; evs[j].pb(TEvent(l, r, x)); if (x == 1) { ++d[j][l]; --d[j][r]; } } } bool ok = true; forn(j, 30) { int b = 0; forn(i, N) { b += d[j][i]; if (b) { p[j][i + 1] = p[j][i] + 1; } else { p[j][i + 1] = p[j][i]; } } forn(i, evs[j].size()) { int s = p[j][evs[j][i].r] - p[j][evs[j][i].l]; if ((s == evs[j][i].r - evs[j][i].l) != evs[j][i].q) ok = false; } } if (!ok) { cout << "NO "; return 0; } cout << "YES "; forn(i, N) { int x = 0; forn(j, 30) x += (p[j][i + 1] - p[j][i]) << j; cout << x << ' '; } cout << ' '; return 0; } |
| 3 | string s[100]; //pii p[1500]; unsigned long long pairs[50][20]; bool nul[1 << 20]; double dp[1 << 20]; int neq[1 << 20]; unsigned long long peq[1 << 20]; int lowbit[1 << 20]; int main() { ios::sync_with_stdio(false); cout.precision(10); cout << fixed; int N; cin >> N; forn(i, N) cin >> s[i]; int L = s[0].size(); //vector<pii> p; //forn(i, N) forn(j, i) p.pb(mp(i, j)); forn(i, 1 << L) { if (!i) { lowbit[i] = -1; continue; } int j = 0; while (!((i >> j) & 1)) ++j; lowbit[i] = j; } forn(i, N) { forn(k, L) { forn(j, N) { if ((i != j) && s[i][k] == s[j][k]) pairs[i][k] += (1LL << j); } } } forn(i, N) { forn(j, 1 << L) { if (!j) peq[0] = (1LL << N) - (1LL << i) - 1; else { int k = lowbit[j]; peq[j] = peq[j - (1 << k)] & pairs[i][k]; } if (peq[j]) ++neq[j]; } } ford(m, 1 << L) { dp[m] = 1.0 * neq[m]; int ss = 0; forn(j, L) { if (!((m >> j) & 1)) ++ss; } forn(j, L) { if (!((m >> j) & 1)) { dp[m] += dp[m | (1 << j)] / ss; } } } printf("%.10lf ", (double)dp[0] / N); return 0; } |
| 4 | const int MAXN = 100000; const i64 P = 1000000000 + 7; i64 ways[MAXN][2]; i64 w[MAXN][2][4]; i64 ww[2][4]; vi e[MAXN]; void dfs(int v) { w[v][1][0] = 1; forn(i, e[v].size()) { int u = e[v][i]; dfs(u); forn(j, 2) forn(k, 4) ww[j][k] = 0; forn(s, 2) forn(j, 2) forn(k, 4) { ww[s ^ j][k | (1 << s)] += w[v][j][k] * ways[u][s]; ww[s ^ j][k | (1 << s)] %= P; } forn(j, 2) forn(k, 4) { w[v][j][k] += ww[j][k]; w[v][j][k] %= P; } } forn(j, 2) forn(k, 4) { int s = 1; if (k == 3 || j == 1 && k == 2) s = 2; ways[v][j] += s * w[v][j][k]; ways[v][j] %= P; } // cerr << v << ' ' << ways[v][0] << ' ' << ways[v][1] << ' '; } int main() { ios::sync_with_stdio(false); cout.precision(10); cout << fixed; int N; cin >> N; forn(i, N - 1) { int x; cin >> x; e[x - 1].pb(i + 1); } dfs(0); i64 ans = ways[0][0] + ways[0][1]; cout << ans % P << ' '; return 0; } |
Комментарии