oj.uz

Submission #926054

# Submission time Handle Problem Language Result Execution time Memory
926054 2024-02-12T13:53:12 Z Joshua_Andersson Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 17528 KB 
#pragma GCC optimize("Ofast,inline,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")//,tune=native")

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

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)

#define _LOCAL _MSC_VER
#if _LOCAL > 0
#define deb __debugbreak();
#define assert(x) debassert(x)
#define popcount(x) __popcnt(x)
#define clz(x) _lzcnt_u32(x)
#else
#define clz(x) __builtin_clz(x)
#define deb ;
#define popcount(x) __builtin_popcountll(x)
#endif

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

#ifdef _DEBUG
#define debassert(expr) if(!(expr)) deb;
#else
#define debassert(expr) ;
#endif

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define sz(container) ((int)container.size())
vector<p2> dirs = { {0,1},{0,-1},{1,0},{-1,0} };

// time and rng
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
random_device rd;
mt19937 rng(rd());
template<typename T, typename U> inline int randint(T lo, U hi) { return uniform_int_distribution<int>((int)lo, (int)hi)(rng); } // [lo,hi]
template<typename T> inline T randel(vector<T>& v) { return v[uniform_int_distribution<int>(int(0), int(v.size()) - int(1))(rng)]; } // [lo,hi]


signed main()
{
	fast();

	string s;
	cin >> s;

	map<char, int> gind;
	vvi groups;
	vvi activegroup;
	int n = sz(s);
	rep(i, n)
	{
		if (!setcontains(gind, s[i])) gind[s[i]] = gind.size(), groups.push_back({});
		groups[gind[s[i]]].push_back(i);
	}
	int g = sz(groups);

	vi groupsz(g);
	rep(i, g)groupsz[i] = sz(groups[i]);
	activegroup.resize(g, vi(n));
	rep(i, g) repe(v, groups[i]) activegroup[i][v] = 1;

	double ans = inf;

	vector<double> exppl(n+1);
	double v = 0;
	double addend = 0;
	repp(i, 1, n+1)
	{
		v += addend;
		addend += 0.5;
		exppl[i] = v;
	}

	auto solvegroup = [&](int groupid, vi& active)
	{
		double best = inf;

		
		vi pref1(n);
		int pref = 0;
		int t = 0;
		rep(i, n)
		{
			if (active[i]) pref += 1;
			if (activegroup[groupid][i]) t += pref;
			pref1[i] = t;
		}
		vi pref2(n);
		pref = 0;
		t = 0;
		for (int i = n - 1; i >= 0; i--)
		{
			if (active[i]) pref += 1;
			if (activegroup[groupid][i]) t += pref;
			pref2[i] = t;
		}
		rep(p, groupsz[groupid] + 1)
		{
			double cost = 0;
			int mid = (p == groupsz[groupid] ? n : groups[groupid][p]);
			if (mid) cost += pref1[mid - 1];
			if (mid < n) cost += pref2[mid];
			best = min(best, cost + exppl[p] + exppl[groupsz[groupid] - p]);
		}
		return best;
	};

	vector<double> dp(1 << g, inf);
	dp[0] = 0;
	rep(mask, 1 << g)
	{
		vi active(n);
		rep(i, g)
		{
			if (mask & (1 << i)) repe(j, groups[i]) active[j] = 1;
		}

		rep(i, g)
		{
			if (mask & (1 << i)) continue;
			dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]+solvegroup(i, active));
		}
	}

	cout << fixed << setprecision(15) << dp.back();

	return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:79:9: warning: unused variable 'ans' [-Wunused-variable]
   79 |  double ans = inf;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 4268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 5172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 5380 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 5380 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 388 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 860 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 860 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 686 ms 1736 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 640 ms 1908 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 639 ms 1860 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 629 ms 1804 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 659 ms 1712 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 670 ms 1704 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 661 ms 1816 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 650 ms 1944 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 656 ms 1792 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 644 ms 1916 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 4268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 5172 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 5380 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 5380 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 388 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 860 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 860 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 686 ms 1736 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 640 ms 1908 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 639 ms 1860 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 629 ms 1804 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 659 ms 1712 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 670 ms 1704 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 661 ms 1816 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 650 ms 1944 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 656 ms 1792 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 644 ms 1916 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 348 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 97 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 344 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 4268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 5208 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 6 ms 5380 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 5380 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 472 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 344 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 856 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 860 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 689 ms 1880 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 608 ms 2124 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 613 ms 1720 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 608 ms 1720 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 656 ms 1792 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 656 ms 1844 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 661 ms 1692 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 647 ms 1688 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 647 ms 1840 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 646 ms 1808 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2064 ms 17528 KB Time limit exceeded
97 Halted 0 ms 0 KB -