oj.uz

Submission #602427

# Submission time Handle Problem Language Result Execution time Memory
602427 2022-07-23T05:49:35 Z slime Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 9168 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); 
  lucas[0] = 2;
  lucas[1] = 1;
  for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
  fib[0] = 0;
  fib[1] = 1;
  for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
  if(l > r) return 0;
  if(l == 0) {
    int s = r / (1ll << (k+1)); // number of complete cycles
    int t = r % (1ll << (k+1));
    int ans = s * (1ll << k);
    ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
    return ans;
  }
  else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
  int n = a.size();
  int bucket[n+1];
  for(int i=1; i<=n; i++) bucket[i] = 1e18;
  int ans = 1;
  for(int x: a) {
    auto it = lower_bound(bucket + 1, bucket +n +1, x);
    int d = distance(bucket, it);
    ans = max(ans, d);
    bucket[d] = min(bucket[d], x);
  }
  return ans;
}
void solve(int tc) {
  string s;
  cin >> s;
  int n = s.size();
  s = " " + s;
  int glob = 0;
  for(int i=0; i<15; i++) {
    bool ok = 0;
    for(int j=1; j<=n; j++) ok |= (s[j] == i + 'A');
    if(ok) glob += (1 << i);
  }
  double dp[glob + 1]; // only consider submasks of glob
  for(int i=0; i<=glob; i++) dp[i] = 1e18;
  dp[0] = 0;
  for(int i=1; i<=glob; i++) {
    if((glob | i) != glob) continue;
    for(int j=0; j<15; j++) {
      if(!(i & (1<<j))) continue;
      int cnt = 0;
      for(int k=1; k<=n; k++) {
        cnt += (s[k] - 'A' == j);
      }
      
      int ppass[cnt + 1], spass[cnt + 2];
      ppass[0] = spass[cnt + 1] = 0;
      int ptr = 0, sum = 0;
      for(int k=1; k<=n; k++) {
        int o = (i & (1 << (s[k] - 'A')));
        if(o ) {
          if(s[k] - 'A' == j) {
            ptr++;
            ppass[ptr] = ppass[ptr - 1] + sum;
          }
          else {
            sum++;
          }
        }
      }
      ptr = cnt + 1, sum = 0;
      for(int k=n; k>=1; k--) {
        int o = (i & (1 << (s[k] - 'A')));
        if(o ) {
          if(s[k] - 'A' == j) {
            ptr--;
            spass[ptr] = spass[ptr + 1] + sum;
          }
          else {
            sum++;
          }
        }
      }
      for(int k=0; k<=cnt; k++) {
        dp[i] = min(dp[i], dp[i - (1<<j)] + k * (k-1) * 0.25 + (cnt-k) * (cnt-k-1) * 0.25 + ppass[k] + spass[k + 1]);
      }
    }
  }
  cout << fixed << setprecision(5) << dp[glob] << "\n";
  //cout << dp[1] << " " << dp[4] << "\n";

} 
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7368 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 8 ms 7272 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 7 ms 7368 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 8 ms 7244 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 8 ms 7280 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 10 ms 8788 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 11 ms 9040 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 10 ms 9168 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 10 ms 9168 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7380 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 7252 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 8 ms 7328 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 8 ms 7372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 9 ms 7252 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 10 ms 7376 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 9 ms 7252 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 9 ms 7376 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 7372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 7344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 10 ms 7252 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 7268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 7252 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 7252 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 7252 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 7372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 7252 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7380 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 7252 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 8 ms 7328 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 8 ms 7372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 9 ms 7252 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 10 ms 7376 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 9 ms 7252 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 9 ms 7376 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 8 ms 7372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 8 ms 7344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 10 ms 7252 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 8 ms 7268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 7 ms 7252 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 8 ms 7252 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 9 ms 7252 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 7 ms 7372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 8 ms 7252 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 8 ms 7252 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 8 ms 7252 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 8 ms 7252 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 8 ms 7356 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 10 ms 7308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 8 ms 7344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 9 ms 7340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 8 ms 7252 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 9 ms 7252 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 9 ms 7252 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 8 ms 7304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 8 ms 7252 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 8 ms 7252 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 8 ms 7252 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 8 ms 7372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 9 ms 7252 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 9 ms 7320 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 8 ms 7508 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 8 ms 7472 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 646 ms 7428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 189 ms 7412 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 199 ms 7544 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 172 ms 7416 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 198 ms 7416 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 200 ms 7416 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 218 ms 7392 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 189 ms 7412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 207 ms 7424 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 195 ms 7380 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7368 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 8 ms 7272 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 7 ms 7368 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 8 ms 7244 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 8 ms 7280 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 10 ms 8788 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 11 ms 9040 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 10 ms 9168 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 10 ms 9168 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 8 ms 7380 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 8 ms 7252 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 8 ms 7328 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 8 ms 7372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 9 ms 7252 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 10 ms 7376 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 9 ms 7252 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 9 ms 7376 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 8 ms 7372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 8 ms 7344 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 10 ms 7252 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 8 ms 7268 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 7 ms 7252 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 8 ms 7252 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 9 ms 7252 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 7 ms 7372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 8 ms 7252 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 8 ms 7252 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 8 ms 7252 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 8 ms 7252 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 8 ms 7356 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 10 ms 7308 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 8 ms 7344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 9 ms 7340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 8 ms 7252 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 9 ms 7252 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 9 ms 7252 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 8 ms 7304 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 8 ms 7252 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 8 ms 7252 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 8 ms 7252 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 8 ms 7372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 9 ms 7252 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 9 ms 7320 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 8 ms 7508 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 8 ms 7472 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 646 ms 7428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 189 ms 7412 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 199 ms 7544 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 172 ms 7416 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 198 ms 7416 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 200 ms 7416 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 218 ms 7392 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 189 ms 7412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 207 ms 7424 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 195 ms 7380 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 8 ms 7516 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 65 ms 7604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 8 ms 7252 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 8 ms 7252 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 9 ms 7252 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 9 ms 7316 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 8 ms 7264 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 10 ms 8784 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 12 ms 8992 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 10 ms 9168 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 11 ms 9168 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 8 ms 7344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 8 ms 7272 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 8 ms 7360 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 7 ms 7252 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 9 ms 7268 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 9 ms 7308 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 9 ms 7252 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 7 ms 7356 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 10 ms 7252 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 8 ms 7252 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 8 ms 7252 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 8 ms 7264 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 8 ms 7320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 8 ms 7352 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 9 ms 7252 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 9 ms 7252 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 8 ms 7252 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 8 ms 7508 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 8 ms 7508 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 650 ms 7400 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 187 ms 7500 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 182 ms 7540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 173 ms 7500 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 196 ms 7404 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 196 ms 7380 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 211 ms 7420 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 198 ms 7408 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 192 ms 7408 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 193 ms 7412 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2073 ms 7980 KB Time limit exceeded
97 Halted 0 ms 0 KB -