oj.uz

Submission #654515

# Submission time Handle Problem Language Result Execution time Memory
654515 2022-10-31T14:47:34 Z cadmiumsky Boarding Passes (BOI22_passes) C++14
0 / 100
 2000 ms 3124 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using ll = long long;
using namespace std;

//#define int ll
//#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

ll dp[1 << 15];
int sum[1 << 15], sz[1 << 15];

signed main() {
  int n;
  string sp;
  vector<int> s;
  cin >> sp;
  n = sp.size();
  dp[0] = 0;
  for(auto &x : sp) x -= 'A', s.emplace_back(1 << x);
  for(int i = 0; i < n; i++) sum[s[i]] += i, sz[s[i]]++;
  for(int i = 1; i < (1 << 15); i++) {
    vector<int> poz;
    vector<ll> alt[2];
    for(int j = 0; j < n; j++) 
      if(s[j] & i) poz.emplace_back(j);
    int total = 0, count = 0;
    alt[0].resize(poz.size());
    alt[1].resize(poz.size());
    
    for(int j = 0; j < 15; j++)
      if((1 << j) & i)
	total += sum[1 << j],
	count += sz[1 << j];
    
    ll mn = n * (n - 1);
    for(int j = 0; j < 15; j++) {
      if(!((1 << j) & i)) continue;
      int remain = (i ^ (1 << j));
      fill(all(alt[0]), 0);
      fill(all(alt[1]), 0);
      if(sz[1 << j] == 0) {
	mn = min(dp[remain], mn);
	continue;
      }
      ll last = 0, cnt = 0;
      
      ll delta = 0, sum = 0;
      for(int i = 0; i < poz.size(); i++) {
	if(s[poz[i]] & remain)
	  sum += poz[i],
	  delta++;
	alt[0][i] = poz[i] * delta - sum;
      }
      
      delta = 0,
      sum = 0;
      for(int i = poz.size() - 1; i >= 0; i--) {
	if(s[poz[i]] & remain)
	  sum += poz[i],
	  delta++;
	alt[1][i] = sum - delta * poz[i];
      }
      
      for(int i = 0; i < poz.size(); i++) {
	if(!(remain & s[poz[i]])) {
	  //cerr << mn << '/' << i << '\t' << dp[remain] << ' ' << alt[0][last] << ' ' << alt[1][last] << ' ' << poz[i] << ' ' << cnt << ' ' << sz[s[poz[i]]] - cnt << '\n';
	  mn = min(dp[remain] + (ll)(alt[0][last] + alt[1][i]) * 2 + (ll)cnt * (cnt - 1) / 2 + (ll)(sz[s[poz[i]]] - cnt) * ((sz[s[poz[i]]] - cnt) - 1) / 2, mn);
	  cnt++;
	  last = i;
	} 
      }
    }
    
    dp[i] = mn;
    //cerr << dp[i] << '\n';
  }
  ll u = dp[(1 << 15) - 1];
  cout << u / 2;
  
  if(u % 2 == 1)
    cout << ".5";
  cout << '\n';
}

/**
      Când iar începe-a ninge
      Mă simt de-un dor cuprins.
      Mă văd, pe-un drum, departe,
      Mergând, încet, şi nins.

      Sub streşină, cerdacul
      Se-ntunecă mâhnit;
      Stă rezimată-o fată
      De stâlpu-nzăpezit.
-- George Bacovia, Ninge
*/

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for(int i = 0; i < poz.size(); i++) {
      |                      ~~^~~~~~~~~~~~
passes.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |       for(int i = 0; i < poz.size(); i++) {
      |                      ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 580 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 8 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 237 ms 460 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2083 ms 3124 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 37 ms 544 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 111 ms 600 KB 1st numbers differ - expected: '1023.0000000000', found: '4578.5000000000', error = '3.4755620723'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 37 ms 544 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 111 ms 600 KB 1st numbers differ - expected: '1023.0000000000', found: '4578.5000000000', error = '3.4755620723'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 580 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 8 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 237 ms 460 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2083 ms 3124 KB Time limit exceeded
7 Halted 0 ms 0 KB -