SCPC 2024 Round 2 코드

 

1. 연속 1

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    int n; ll s, e; cin >> n >> s >> e;
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    ll mn = b[n] * e, dp = 0;
    for (int i = 1; i <= n; i++) {
        dp = min(dp, b[i - 1] * e) + (!a[i]) * s;
        mn = min(mn, dp + (b[n] - b[i]) * e);
    }
    cout << mn << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

 

 

2. 라운드 로빈

 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 1e5 + 1;

ll a[N], b[N];
pair<ll, int> qry[N];
ordered_set st;

void solve() {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> b[i];

    map<ll, vector<int>> mp;
    for (int i = 1; i <= n; i++) mp[a[i]].push_back(i);
    for (int i = 0; i < q; i++) qry[i] = {b[i], i};
    sort(qry, qry + q);

    for (int i = 1; i <= n; i++) st.insert(i);
    ll t = 0, x = 0, p = 0, ans = 0;
    for (auto &[k, v] : mp) {
        while (t < q && qry[t].first <= x + (k - p) * st.size()) {
            auto [y, i] = qry[t++];
            y = (y - x - 1) % st.size();
            ans += *st.find_by_order(y);
        }
        x += (k - p) * st.size(), p = k;
        for (auto &z : v) st.erase(z);
    }
    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

 

 

3. 방범 시스템

 

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int N = 1e5 + 1;

pair<int, double> a[2][N];
double b[2][N], c[2][N];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[0][i].fi >> a[1][i].fi;
    for (int i = 1; i <= n; i++) cin >> a[0][i].se, a[1][i].se = a[0][i].se;
    for (int t : {0, 1}) sort(a[t] + 1, a[t] + n + 1);
    for (int t : {0, 1}) for (int i = 1; i <= n; i++) b[t][i] = b[t][i - 1] + a[t][i].fi * a[t][i].se;
    for (int t : {0, 1}) for (int i = 1; i <= n; i++) c[t][i] = c[t][i - 1] + a[t][i].se;

    int q; cin >> q;
    while (q--) {
        int x[2]; cin >> x[0] >> x[1];
        double ans = 0;
        for (int t : {0, 1}) {
            int l = 0, r = n;
            if (a[t][n].fi < x[t]) l = n;
            else if (a[t][1].fi < x[t]) {
                l = 1;
                while (l + 1 < r) {
                    int m = l + r >> 1;
                    (a[t][m].fi < x[t] ? l : r) = m;
                }
            }
            ans += c[t][l] * x[t] - b[t][l];
            ans += b[t][n] - b[t][l] - (c[t][n] - c[t][l]) * x[t];
        }
        cout << ans << '\n';
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(9);
    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

 

 

4. 수열 탈집중화 (시행 횟수가 1이 아닐 때 틀림) (아래는 수정본, 아마 맞음)

 

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int N = 50001;

int a[N];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int mn = *min_element(a + 1, a + n + 1);
    int mx = *max_element(a + 1, a + n + 1);

    if (mn == mx) {
        cout << 0 << '\n';
        return;
    }
    {
        int cn = 0, cx = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == mn) cn++;
            if (a[i] == mx) cx++;
        }
        if (cn + cx == n && abs(cn - cx) <= 1) {
            cout << 0 << '\n';
            return;
        }
    }
    {
        int cn = 0, cx = 0, dl = 0, dr = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == mn) cn++;
            else if (a[i] == mx) cx++;
            else dl = dl ? dl : i, dr = i;
        }
        if (dl) {
            if (cn >= n / 2 && cx >= n / 2) {
                cout << 1 << '\n';
                assert(dl == dr);
                if (dl > 1) cout << 1 + (a[dl - 1] != mn) << ' ' << dl - 1 << ' ' << dl << '\n';
                else cout << 1 + (a[dl + 1] != mn) << ' ' << dl << ' ' << dl + 1 << '\n';
                return;
            }
            else if (cn >= n / 2) {
                int p = 0, q = 0, s = 0;
                for (int i = dl - 1; i >= 1; i--) if (a[i] == mx) { p = i; break; }
                for (int i = dl; i <= dr; i++) if (a[i] == mx) q = i;
                for (int i = dr + 1; i <= n; i++) if (a[i] == mx) { s = i; break; }
                int L[3] = {}, R[3] = {};
                if (p) L[0] = p, R[0] = dr;
                if (q) L[1] = dl, R[1] = dr;
                if (R) L[2] = dl, R[2] = s;
                for (int t : {0, 1, 2}) if (L[t]) {
                    int l = L[t], r = R[t];
                    cn = 0;
                    for (int i = 1; i < l; i++) cn += a[i] == mn;
                    for (int i = r + 1; i <= n; i++) cn += a[i] == mn;
                    if (cn >= n / 2) {
                        int tt = cn - n / 2;
                        while (l > 1 && tt) if (a[--l] ^ mx) tt--;
                        while (tt) if (a[++r] ^ mx) tt--;
                        cout << 1 << '\n';
                        cout << 2 << ' ' << l << ' ' << r << '\n';
                        return;
                    }
                }
            }
            else if (cx >= n / 2) {
                int p = 0, q = 0, s = 0;
                for (int i = dl - 1; i >= 1; i--) if (a[i] == mn) { p = i; break; }
                for (int i = dl; i <= dr; i++) if (a[i] == mn) q = i;
                for (int i = dr + 1; i <= n; i++) if (a[i] == mn) { s = i; break; }
                int L[3] = {}, R[3] = {};
                if (p) L[0] = p, R[0] = dr;
                if (q) L[1] = dl, R[1] = dr;
                if (R) L[2] = dl, R[2] = s;
                for (int t : {0, 1, 2}) if (L[t]) {
                    int l = L[t], r = R[t];
                    cx = 0;
                    for (int i = 1; i < l; i++) cx += a[i] == mx;
                    for (int i = r + 1; i <= n; i++) cx += a[i] == mx;
                    if (cx >= n / 2) {
                        int tt = cx - n / 2;
                        while (l > 1 && tt) if (a[--l] ^ mn) tt--;
                        while (tt) if (a[++r] ^ mn) tt--;
                        cout << 1 << '\n';
                        cout << 1 << ' ' << l << ' ' << r << '\n';
                        return;
                    }
                }
            }
        }
        else if (cn < cx) {
            int l = 0, r = 0, t = n / 2 - cn;
            for (int i = 1; i <= n; i++) {
                if (a[i] == mn) {
                    l = r = i;
                    break;
                }
            }
            while (l > 1 && t) if (a[--l] ^ mn) t--;
            while (t) if (a[++r] ^ mn) t--;
            cout << 1 << '\n';
            cout << 1 << ' ' << l << ' ' << r << '\n';
            return;
        }
        else {
            int l = 0, r = 0, t = n / 2 - cx;
            for (int i = 1; i <= n; i++) {
                if (a[i] == mx) {
                    l = r = i;
                    break;
                }
            }
            while (l > 1 && t) if (a[--l] ^ mx) t--;
            while (t) if (a[++r] ^ mx) t--;
            cout << 1 << '\n';
            cout << 2 << ' ' << l << ' ' << r << '\n';
            return;
        }
    }
    {
        cout << 2 << '\n';
        int mni = 0, mxi = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == mn) mni = i;
            if (a[i] == mx) mxi = i;
        }
        if (mni < mxi) {
            if (mxi > n / 2) {
                cout << 1 << ' ' << 1 << ' ' << mxi - 1 << '\n';
                cout << 2 << ' ' << n / 2 + 1 << ' ' << n << '\n';
            }
            else {
                cout << 2 << ' ' << mni + 1 << ' ' << n << '\n';
                cout << 1 << ' ' << 1 << ' ' << n / 2 << '\n';
            }
        }
        else {
            if (mni > n / 2) {
                cout << 2 << ' ' << 1 << ' ' << mni - 1 << '\n';
                cout << 1 << ' ' << n / 2 + 1 << ' ' << n << '\n';
            }
            else {
                cout << 1 << ' ' << mxi + 1 << ' ' << n << '\n';
                cout << 2 << ' ' << 1 << ' ' << n / 2 << '\n';
            }
        }
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

 

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int N = 50001;

int a[N];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int mn = *min_element(a + 1, a + n + 1);
    int mx = *max_element(a + 1, a + n + 1);

    if (mn == mx) {
        cout << 0 << '\n';
        return;
    }
    {
        int cn = 0, cx = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == mn) cn++;
            if (a[i] == mx) cx++;
        }
        if (cn + cx == n && abs(cn - cx) <= 1) {
            cout << 0 << '\n';
            return;
        }
    }
    {
        int cn = 0, cx = 0, dl = 0, dr = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == mn) cn++;
            else if (a[i] == mx) cx++;
            else dl = dl ? dl : i, dr = i;
        }
        if (dl) {
            if (cn >= n / 2 && cx >= n / 2) {
                cout << 1 << '\n';
                assert(dl == dr);
                if (dl > 1) cout << 1 + (a[dl - 1] != mn) << ' ' << dl - 1 << ' ' << dl << '\n';
                else cout << 1 + (a[dl + 1] != mn) << ' ' << dl << ' ' << dl + 1 << '\n';
                return;
            }
            else if (cn >= n / 2) {
                int p = 0, q = 0, s = 0;
                for (int i = dl - 1; i >= 1; i--) if (a[i] == mx) { p = i; break; }
                for (int i = dl; i <= dr; i++) if (a[i] == mx) q = i;
                for (int i = dr + 1; i <= n; i++) if (a[i] == mx) { s = i; break; }
                int L[3] = {}, R[3] = {};
                if (p) L[0] = p, R[0] = dr;
                if (q) L[1] = dl, R[1] = dr;
                if (s) L[2] = dl, R[2] = s;
                for (int t : {0, 1, 2}) if (L[t]) {
                    int l = L[t], r = R[t];
                    cn = 0;
                    for (int i = 1; i < l; i++) cn += a[i] == mn;
                    for (int i = r + 1; i <= n; i++) cn += a[i] == mn;
                    if (cn >= n / 2) {
                        int tt = cn - n / 2;
                        while (l > 1 && tt) if (a[--l] ^ mx) tt--;
                        while (tt) if (a[++r] ^ mx) tt--;
                        cout << 1 << '\n';
                        cout << 2 << ' ' << l << ' ' << r << '\n';
                        return;
                    }
                }
            }
            else if (cx >= n / 2) {
                int p = 0, q = 0, s = 0;
                for (int i = dl - 1; i >= 1; i--) if (a[i] == mn) { p = i; break; }
                for (int i = dl; i <= dr; i++) if (a[i] == mn) q = i;
                for (int i = dr + 1; i <= n; i++) if (a[i] == mn) { s = i; break; }
                int L[3] = {}, R[3] = {};
                if (p) L[0] = p, R[0] = dr;
                if (q) L[1] = dl, R[1] = dr;
                if (s) L[2] = dl, R[2] = s;
                for (int t : {0, 1, 2}) if (L[t]) {
                    int l = L[t], r = R[t];
                    cx = 0;
                    for (int i = 1; i < l; i++) cx += a[i] == mx;
                    for (int i = r + 1; i <= n; i++) cx += a[i] == mx;
                    if (cx >= n / 2) {
                        int tt = cx - n / 2;
                        while (l > 1 && tt) if (a[--l] ^ mn) tt--;
                        while (tt) if (a[++r] ^ mn) tt--;
                        cout << 1 << '\n';
                        cout << 1 << ' ' << l << ' ' << r << '\n';
                        return;
                    }
                }
            }
        }
        else if (cn < cx) {
            int l = 0, r = 0, t = n / 2 - cn;
            for (int i = 1; i <= n; i++) {
                if (a[i] == mn) {
                    l = r = i;
                    break;
                }
            }
            while (l > 1 && t) if (a[--l] ^ mn) t--;
            while (t) if (a[++r] ^ mn) t--;
            cout << 1 << '\n';
            cout << 1 << ' ' << l << ' ' << r << '\n';
            return;
        }
        else {
            int l = 0, r = 0, t = n / 2 - cx;
            for (int i = 1; i <= n; i++) {
                if (a[i] == mx) {
                    l = r = i;
                    break;
                }
            }
            while (l > 1 && t) if (a[--l] ^ mx) t--;
            while (t) if (a[++r] ^ mx) t--;
            cout << 1 << '\n';
            cout << 2 << ' ' << l << ' ' << r << '\n';
            return;
        }
    }
    {
        cout << 2 << '\n';
        int mni = 0, mxi = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == mn) mni = i;
            if (a[i] == mx) mxi = i;
        }
        if (mni < mxi) {
            if (mxi > n / 2) {
                cout << 1 << ' ' << 1 << ' ' << mxi - 1 << '\n';
                cout << 2 << ' ' << n / 2 + 1 << ' ' << n << '\n';
            }
            else {
                cout << 2 << ' ' << mni + 1 << ' ' << n << '\n';
                cout << 1 << ' ' << 1 << ' ' << n / 2 << '\n';
            }
        }
        else {
            if (mni > n / 2) {
                cout << 2 << ' ' << 1 << ' ' << mni - 1 << '\n';
                cout << 1 << ' ' << n / 2 + 1 << ' ' << n << '\n';
            }
            else {
                cout << 1 << ' ' << mxi + 1 << ' ' << n << '\n';
                cout << 2 << ' ' << 1 << ' ' << n / 2 << '\n';
            }
        }
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

 

 

5. 보물찾기 (A에 T가 없을 때, 풀태 틀림)

 

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int N = 1e5 + 1;

int par[N], sz[N];

void init(int n) {
	iota(par, par + n + 1, 0);
	fill(sz + 1, sz + n + 1, 1);
}
int fnd(int v) {
	if(par[v] == v) return v;
	return par[v] = fnd(par[v]);
}
void uni(int u, int v) {
	u = fnd(u), v = fnd(v);
	if(u == v) return;
	if(sz[u] < sz[v]) swap(u, v);
	par[v] = u, sz[u] += sz[v];
}

vector<int> ad[N];
vector<int> da[N];

void solve() {
    int n, m; cin >> n >> m;
    init(n);
    string s, t; cin >> s >> t;
    s = '.' + s, t = '.' + t;
    for (int i = 1; i <= n; i++) ad[i].clear();
    while (m--) {
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
        if (s[u] == s[v]) uni(u, v);
    }
    for (int i = 1; i <= n; i++) fnd(i);
    vector<int> idx = {0}, ord(n + 1);
    for (int i = 1; i <= n; i++) if (par[i] == i) idx.push_back(i);
    m = idx.size() - 1;
    for (int i = 1; i <= m; i++) ord[idx[i]] = i;
    vector<bool> tt(m + 1), fl(m + 1);
    for (int i = 1; i <= n; i++) if (t[i] == 'T') tt[ord[par[i]]] = 1;
    for (int i = 1; i <= n; i++) for (int &j : ad[i]) {
        if (s[i] == 'B' && s[j] == 'B' && t[i] == '.' && t[j] == '.') fl[ord[par[i]]] = 1;
    }
    vector<int> _sz(m + 1), tp(m + 1), ans(m + 1), id(m + 1);
    for (int i = 1; i <= n; i++) _sz[ord[par[i]]]++;
    for (int i = 1; i <= m; i++) {
        if (s[idx[i]] == 'A') {
            if (tt[i]) tp[i] = _sz[i] > 1 ? 1 : 2, ans[i] = 1;
            else tp[i] = 3;
        }
        else {
            tp[i] = fl[i] ? 4 : 5;
        }
    }
    for (int i = 1; i <= m; i++) da[i].clear();
    for (int i = 1; i <= n; i++) for (int &j : ad[i]) {
        int u = ord[par[i]], v = ord[par[j]];
        if (tp[u] == 3 && tp[v] == 5) {
            if (t[j] == '.') da[u].push_back(v), id[v]++;
        }
        if (tp[u] == 5 && tp[v] == 3) da[u].push_back(v);
        if (tp[u] == 2 && tp[v] == 5) da[u].push_back(v);
    }
    queue<int> q;
    for (int i = 1; i <= m; i++) if (tp[i] == 5 && !id[i]) q.push(i);
    while (q.size()) {
        auto u = q.front(); q.pop();
        ans[u] = 1;
        for (int &v : da[u]) if(!ans[v]) {
            ans[v] = 1;
            for (int &uu : da[v]) if (!--id[uu] && !ans[uu]) q.push(uu);
        }
    }
    for (int i = 1; i <= m; i++) if (tp[i] == 2) {
        ans[i] = 0;
        for (int &j : da[i]) if (ans[j]) ans[i] = 1;
    }
    string anss;
    for (int i = 1; i <= n; i++) anss += "BA"[ans[ord[par[i]]]];
    cout << anss << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}