이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <queue>
#include <iomanip>
#include <cmath>
#include <string>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<vll> vvll;
typedef vector<vld> vvld;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef set<ll> sll;
typedef set<pll> spll;
typedef map<pll, ll> mpll_ll;
typedef map<ll, pll> mll_pll;
typedef bitset<15> bits;
typedef vector<bits> vbits;
typedef string str;
typedef vector<str> vstr;
#define rep(x, a, b) for (int x = a; x < b; x++)
#define rev_rep(x, a, b) for (int x = a; x >= b; x--)
#define itr_rep(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, b) a.resize(b)
#define sort_all(a) sort(all(a))
#define pb(a) push_back(a)
#define fill_sz(a, b) fill_n(a.begin(), sz(a), b)
const ll MAXN = 100000;
const ll MAXG = 15;
const ld INF = MAXN * MAXN;
ll N, G;
string s;
vvll groups;
vvll prefix_sums;
vvvll passes;
struct Comparer {
bool operator() (const bitset<15> &b1, const bitset<15> &b2) const {
return (b1.to_ulong() < b2.to_ulong());
}
};
bits active(0x0);
map<bits, vld, Comparer> dp_diff;
map<bits, ld, Comparer> dp;
ld calc_passes(ll i, ll k) {
ld answ = 0;
rep(j, 0, G) {
if (!active[j]) {continue;}
answ += passes[i][j][k];
}
answ += ((ld) k * (k - 1)) / 4;
answ += ((ld) (sz(groups[i]) - k) * (sz(groups[i]) - k - 1)) / 4;
return answ;
}
void dp_diff_DFS(ll depth=0) {
if (depth != G) {
dp_diff_DFS(depth + 1);
active[depth] = true;
dp_diff_DFS(depth + 1);
active[depth] = false;
return;
}
resz(dp_diff[active], G);
rep(i, 0, G) {
if (active[i]) {continue;}
// consider the best way to have ppl from group i board given that groups in active have boarded, store this in dp
// use ternary search...
ll l = 0;
ll r = sz(groups[i]);
while (r - l > 2) {
ll m1 = l + (r - l) / 3;
ll m2 = r - (r - l) / 3;
ld f1 = calc_passes(i, m1);
ld f2 = calc_passes(i, m2);
if (f1 > f2) {
l = m1;
} else {
r = m2;
}
}
dp_diff[active][i] = calc_passes(i, l);
rep(c, l + 1, r + 1) {
dp_diff[active][i] = min<ld>(dp_diff[active][i], calc_passes(i, c));
}
//dp_diff[active][i] = min<ld>(calc_passes(i, l), calc_passes(i, r));
}
}
ld dp_recursion(bits call) {
if (dp.count(call)) {return dp[call];}
ld answ = INF;
rep (i, 0, G) {
if (!call[i]) {continue;}
call[i] = false;
answ = min<ld>(answ, dp_recursion(call) + dp_diff[call][i]);
call[i] = true;
}
dp[call] = answ;
return dp[call];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(15);
cin >> s;
N = sz(s);
G = 0;
rep(i, 0, N) {
while (s[i] - 'A' >= G) {
G++;
groups.pb(vll());
}
groups[s[i] - 'A'].pb(i);
}
// calculate prefix sums
resz(prefix_sums, G);
rep(i, 0, G) {
resz(prefix_sums[i], N + 1);
prefix_sums[i][0] = 0;
rep(j, 0, N) {
prefix_sums[i][j + 1] = prefix_sums[i][j] + (s[j] - 'A' == i);
}
}
// calculate passes between groups
resz(passes, G);
rep(i, 0, G) {
resz(passes[i], G);
rep(j, 0, G) {
resz(passes[i][j], sz(groups[i]) + 1);
fill_sz(passes[i][j], 0);
// calculate the number of cumulative passes if first k of group i enter from front, and remaining |g|i]| - k enter from back
// from front
ll running_cumulative = 0;
rep(k, 1, sz(groups[i]) + 1) {
running_cumulative += prefix_sums[j][groups[i][k - 1]];
passes[i][j][k] += running_cumulative;
}
// from back
running_cumulative = 0;
rev_rep(k, sz(groups[i]) - 1, 0) {
running_cumulative += prefix_sums[j][N] - prefix_sums[j][groups[i][k]];
passes[i][j][k] += running_cumulative;
}
// we have made sure that groups[i][k] is _excluded_ from counting as passed, as this makes the passes[e][e] case correct
}
}
// calc subset dp
dp_diff_DFS();
// find optimal route...
bits call(0x0);
dp[call] = 0;
rep(i, 0, G) {if (sz(groups[i])) {call[i] = true;}}
cout << dp_recursion(call) << endl;
return 0;
}
// for each pair of groups, need to know the number of passes if first k enter from front, and last |g[i]| - k enter from back
컴파일 시 표준 에러 (stderr) 메시지
passes.cpp: In function 'int main()':
passes.cpp:36:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | #define rep(x, a, b) for (int x = a; x < b; x++)
......
167 | rep(k, 1, sz(groups[i]) + 1) {
| ~~~~~~~~~~~~~~~~~~~~~~~
passes.cpp:167:13: note: in expansion of macro 'rep'
167 | rep(k, 1, sz(groups[i]) + 1) {
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |