oj.uz

Submission #925895

# Submission time Handle Problem Language Result Execution time Memory
925895 2024-02-12T10:29:29 Z Joshua_Andersson Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 2988 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;
		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;
	};

	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 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 508 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2073 ms 2988 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 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 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 1 ms 344 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 348 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 1 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 3 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 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 1 ms 344 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 348 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 1 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 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 3 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 3 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 3 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 348 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 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 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 284 ms 836 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 276 ms 852 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2095 ms 1368 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 348 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 508 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2073 ms 2988 KB Time limit exceeded
7 Halted 0 ms 0 KB -