oj.uz

Submission #580511

# Submission time Handle Problem Language Result Execution time Memory
580511 2022-06-21T11:16:15 Z haojiandan Boarding Passes (BOI22_passes) C++14
0 / 100
 1 ms 340 KB 
// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const int maxn=(1e4)+10;
int n,N;
char s[maxn*10],lsh[maxn*10];
int m,pre[1<<10][maxn],suf[1<<10][maxn];
vector<int> vec[30];
double dp[1<<10];
int main() {
	scanf("%s",s+1); n=strlen(s+1);
	for (int i=1;i<=n;i++) lsh[++N]=s[i];
	sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
	for (int i=1;i<=n;i++) s[i]=lower_bound(lsh+1,lsh+N+1,s[i])-lsh+'A'-1;
	for (int i=1;i<=n;i++) m=max(m,s[i]-'A'),vec[s[i]-'A'].push_back(i);
	if (m==0) {
		m=n/2;
		double ans=m*0.5*(m-1)+(n-m)*0.5*(n-m-1);
		ans*=0.5;
		printf("%.6lf\n",ans);
		return 0;
	}
	m++;
	for (int t=0;t<(1<<m);t++) {
		for (int i=1;i<=n;i++) pre[t][i]=pre[t][i-1]+(t>>(s[i]-'A')&1);
		for (int i=n;i>=1;i--) suf[t][i]=suf[t][i+1]+(t>>(s[i]-'A')&1);
		dp[t]=1e18;
	}
	dp[0]=0;
	for (int t=0;t<(1<<m);t++) {
		for (int i=0;i<m;i++) if (!(t>>i&1)) {
			double tmp=0;
			for (int &x : vec[i]) tmp+=min(pre[t][x]+pre[1<<i][x-1]*0.5,suf[t][x]+suf[1<<i][x+1]*0.5);
			dp[t^(1<<i)]=min(dp[t^(1<<i)],dp[t]+tmp);
		}
	}
	printf("%.6lf\n",dp[(1<<m)-1]);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%s",s+1); n=strlen(s+1);
      |  ~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -