oj.uz

Submission #925876

# Submission time Handle Problem Language Result Execution time Memory
925876 2024-02-12T10:18:52 Z Joshua_Andersson Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 2984 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 perm(g);
	rep(i, g)perm[i] = i;
	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;
		rep(p, groupsz[groupid] + 1)
		{
			double cost = 0;
			int mid = (p == groupsz[groupid] ? n : groups[groupid][p]);
			int pref = 0;
			rep(i, mid)
			{
				if (active[i]) pref += 1;
				if (activegroup[groupid][i]) cost += pref;
			}
			pref = 0;
			for (int i = n - 1; i >= mid; i--)
			{
				if (active[i]) pref += 1;
				if (activegroup[groupid][i]) cost += pref;
			}
			best = min(best, cost + exppl[p] + exppl[groupsz[groupid] - p]);
		}
		return best;
	};

	do
	{
		vi active(n);
		double cost = 0;
		rep(i, g)
		{
			int groupid = perm[i];

			cost += solvegroup(groupid, active);

			repe(v, groups[groupid]) active[v] = 1;
		}
		ans = min(ans, cost);

	} while (next_permutation(all(perm)));

	cout << fixed << setprecision(15) << ans;

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 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 3 ms 504 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2045 ms 2984 KB Time limit exceeded
7 Halted 0 ms 0 KB -

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 227 ms 456 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 182 ms 452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 175 ms 456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 5 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 147 ms 448 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 20 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 20 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 20 ms 472 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 20 ms 472 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 20 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 20 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
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 227 ms 456 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 182 ms 452 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 175 ms 456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 5 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 147 ms 448 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 3 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 20 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 20 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 20 ms 472 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 20 ms 472 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 20 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 20 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 20 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 344 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 206 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 183 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 176 ms 456 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 5 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 148 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 4 ms 504 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 20 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 20 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 20 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 20 ms 472 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 20 ms 472 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 22 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 20 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 23 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 20 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 280 ms 856 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 301 ms 856 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2059 ms 1372 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 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 3 ms 504 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2045 ms 2984 KB Time limit exceeded
7 Halted 0 ms 0 KB -