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();
}
}
'Contest > SCPC' 카테고리의 다른 글
SCPC 2024 Round 1 코드 (0) | 2024.07.05 |
---|---|
SCPC 2023 본선 후기 (9) | 2023.09.19 |
SCPC 2023 2차 예선 후기 (2) | 2023.08.20 |
SCPC 2023 1차 예선 후기 (5) | 2023.08.03 |