oj.uz

Submission #926091

# Submission time Handle Problem Language Result Execution time Memory
926091 2024-02-12T14:44:13 Z Joshua_Andersson Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 366444 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]

int precomp1[15][15][int(1e5)];
int precomp2[15][15][int(1e5)];

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;
	}

	memset(precomp1, 0, sizeof(precomp1));
	memset(precomp2, 0, sizeof(precomp2));

	rep(a, g)
	{
		rep(b, g)
		{
			int pref = 0;
			int t = 0;
			rep(i, n)
			{
				if (activegroup[a][i]) pref += 1;
				if (activegroup[b][i]) t += pref;
				precomp1[a][b][i] = t;
			}
			
			pref = 0;
			t = 0;
			per(i, n)
			{
				if (activegroup[a][i]) pref += 1;
				if (activegroup[b][i]) t += pref;
				precomp2[a][b][i] = t;
			}
		}
	}

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

		
		rep(p, groupsz[groupid] + 1)
		{
			double cost = 0;
			int mid = (p == groupsz[groupid] ? n : groups[groupid][p]);

			rep(j, g)
			{
				if ((mask & (1 << j)) == 0) continue;
				if (mid) cost += precomp1[j][groupid][mid-1];
				if (mid<n) cost += precomp2[j][groupid][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)
	{
		rep(i, g)
		{
			if (mask & (1 << i)) continue;
			dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]+solvegroup(mask, i));
		}
	}

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

	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 352592 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 41 ms 352548 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 40 ms 352596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 40 ms 352592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 40 ms 352596 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 44 ms 354740 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 43 ms 355116 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 44 ms 355068 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 44 ms 355068 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 352596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 42 ms 352528 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 41 ms 352556 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 41 ms 352596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 41 ms 352548 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 41 ms 352604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 40 ms 352592 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 41 ms 352528 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 40 ms 352520 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 352592 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 40 ms 352592 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 352596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 352548 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 41 ms 352596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 41 ms 352660 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 40 ms 352772 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 41 ms 352624 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 352596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 42 ms 352528 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 41 ms 352556 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 41 ms 352596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 41 ms 352548 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 41 ms 352604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 40 ms 352592 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 41 ms 352528 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 40 ms 352520 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 41 ms 352592 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 40 ms 352592 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 41 ms 352596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 41 ms 352548 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 41 ms 352596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 41 ms 352660 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 40 ms 352772 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 41 ms 352624 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 40 ms 352596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 41 ms 352596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 41 ms 352636 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 41 ms 352592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 42 ms 352540 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 41 ms 352596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 41 ms 352572 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 42 ms 352672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 41 ms 352596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 44 ms 352604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 41 ms 352596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 41 ms 352544 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 40 ms 352600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 42 ms 352596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 41 ms 352688 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 41 ms 352540 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 44 ms 352596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 41 ms 352784 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 41 ms 352848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 135 ms 353568 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 128 ms 353536 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 121 ms 353876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 119 ms 353616 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 150 ms 353616 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 129 ms 353616 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 133 ms 353696 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 127 ms 353672 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 133 ms 353684 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 143 ms 353876 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 352592 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 41 ms 352548 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 40 ms 352596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 40 ms 352592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 40 ms 352596 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 44 ms 354740 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 43 ms 355116 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 44 ms 355068 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 44 ms 355068 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 41 ms 352596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 42 ms 352528 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 41 ms 352556 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 41 ms 352596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 41 ms 352548 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 41 ms 352604 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 40 ms 352592 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 41 ms 352528 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 40 ms 352520 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 41 ms 352592 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 40 ms 352592 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 41 ms 352596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 41 ms 352548 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 41 ms 352596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 41 ms 352660 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 40 ms 352772 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 41 ms 352624 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 40 ms 352596 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 41 ms 352596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 41 ms 352636 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 41 ms 352592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 42 ms 352540 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 41 ms 352596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 41 ms 352572 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 42 ms 352672 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 41 ms 352596 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 44 ms 352604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 41 ms 352596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 41 ms 352544 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 40 ms 352600 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 42 ms 352596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 41 ms 352688 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 41 ms 352540 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 44 ms 352596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 41 ms 352784 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 41 ms 352848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 135 ms 353568 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 128 ms 353536 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 121 ms 353876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 119 ms 353616 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 150 ms 353616 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 129 ms 353616 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 133 ms 353696 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 127 ms 353672 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 133 ms 353684 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 143 ms 353876 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 42 ms 352536 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 83 ms 352852 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 41 ms 352592 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 44 ms 352592 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 41 ms 352472 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 41 ms 352592 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 41 ms 352600 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 43 ms 354716 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 44 ms 355092 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 45 ms 355068 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 44 ms 355064 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 43 ms 352852 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 42 ms 352596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 42 ms 352592 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 41 ms 352596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 41 ms 352592 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 41 ms 352596 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 42 ms 352852 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 41 ms 352604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 42 ms 352668 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 41 ms 352596 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 41 ms 352592 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 41 ms 352596 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 41 ms 352596 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 42 ms 352592 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 41 ms 352548 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 40 ms 352572 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 40 ms 352596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 41 ms 352852 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 42 ms 352848 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 138 ms 353804 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 119 ms 353620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 121 ms 353684 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 140 ms 353668 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 125 ms 353540 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 132 ms 353524 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 125 ms 353620 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 135 ms 353876 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 129 ms 353516 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 137 ms 353680 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2066 ms 366444 KB Time limit exceeded
97 Halted 0 ms 0 KB -