oj.uz

Submission #604827

# Submission time Handle Problem Language Result Execution time Memory
604827 2022-07-25T10:10:33 Z errorgorn Boarding Passes (BOI22_passes) C++17
100 / 100
 1623 ms 706508 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int BUF=100005;

struct node{
	int arr[200010]={};
	
	int query(int i,int j){
		i+=BUF,j+=BUF+1;
		
		int res=0;
		while (i<j){
			if (i&1) res+=arr[i++];
			if (j&1) res+=arr[--j];
			i>>=1,j>>=1;
		}
		return res;
	}
};

int n;
string s;
vector<int> pos[15];

node root[15][15][2];

int cnt[15];

int get0(int u,int mask,int l,int r){
	int res=0;
	rep(v,0,15) if (mask&(1<<v)) res+=root[u][v][0].query(l,r);
	return res;
}

int get1(int u,int mask,int l,int r){
	int res=0;
	rep(v,0,15) if (mask&(1<<v)) res+=root[u][v][1].query(l,r);
	return res;
}

int memo[1<<15];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>s;
	n=sz(s);
	
	rep(x,0,n) pos[s[x]-'A'].pub(x);
	
	rep(x,0,n){
		rep(y,0,15) root[s[x]-'A'][y][0].arr[x+BUF]=cnt[y]*(s[x]-'A'==y?1:2);
		cnt[s[x]-'A']++;
	}
	
	memset(cnt,0,sizeof(cnt));
	
	rep(x,n,0){
		rep(y,0,15) root[s[x]-'A'][y][1].arr[x+BUF]=cnt[y]*(s[x]-'A'==y?1:2);
		cnt[s[x]-'A']++;
	}
	
	rep(x,0,15) rep(y,0,15) rep(z,0,2) rep(i,BUF,0){
		root[x][y][z].arr[i]=root[x][y][z].arr[i<<1]+root[x][y][z].arr[i<<1|1];
	}
	
	memset(memo,63,sizeof(memo));
	memo[0]=0;
	
	rep(mask,0,1<<15) rep(bit,0,15) if ((mask&(1<<bit))==0){
		int nm=mask|(1<<bit);
		int lo=-1,hi=sz(pos[bit]),mi;
		
		while (hi-lo>1){
			mi=hi+lo>>1;
			
			if (get0(bit,nm,pos[bit][mi],pos[bit][mi]) < get1(bit,nm,pos[bit][mi],pos[bit][mi])){
				lo=mi;
			}
			else{
				hi=mi;
			}
		}
		
		int res=memo[mask];
		if (0<=lo) res+=get0(bit,nm,0,pos[bit][lo]);
		if (hi<sz(pos[bit])) res+=get1(bit,nm,pos[bit][hi],100004);
		memo[nm]=min(memo[nm],res);
	}
	
	int ans=memo[(1<<15)-1];
	
	cout<<ans/2; if (ans%2) cout<<".5"; cout<<endl;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:97:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |    mi=hi+lo>>1;
      |       ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 355548 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 227 ms 355224 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 240 ms 355316 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 240 ms 355240 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 235 ms 355472 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 255 ms 374728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 291 ms 378440 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 263 ms 379780 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 289 ms 379888 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 355232 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 229 ms 355348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 346 ms 355472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 282 ms 355376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 277 ms 355352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 266 ms 355268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 322 ms 355344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 287 ms 355360 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 307 ms 355272 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 295 ms 355300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 289 ms 355420 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 308 ms 355256 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 315 ms 355476 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 322 ms 355356 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 300 ms 355268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 328 ms 355352 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 295 ms 355336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 355232 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 229 ms 355348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 346 ms 355472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 282 ms 355376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 277 ms 355352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 266 ms 355268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 322 ms 355344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 287 ms 355360 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 307 ms 355272 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 295 ms 355300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 289 ms 355420 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 308 ms 355256 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 315 ms 355476 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 322 ms 355356 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 300 ms 355268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 328 ms 355352 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 295 ms 355336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 249 ms 355272 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 242 ms 355244 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 320 ms 355480 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 360 ms 355344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 281 ms 355276 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 308 ms 355324 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 349 ms 355448 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 325 ms 355352 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 315 ms 355356 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 313 ms 355308 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 298 ms 355244 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 331 ms 355352 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 315 ms 355304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 336 ms 355356 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 301 ms 355276 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 329 ms 355424 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 297 ms 355252 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 265 ms 357816 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 255 ms 357904 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 624 ms 378900 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 427 ms 358748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 308 ms 357796 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 582 ms 366468 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 629 ms 378412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 650 ms 378388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 629 ms 378412 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 597 ms 378404 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 588 ms 378408 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 619 ms 378400 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 355548 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 227 ms 355224 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 240 ms 355316 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 240 ms 355240 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 235 ms 355472 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 255 ms 374728 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 291 ms 378440 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 263 ms 379780 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 289 ms 379888 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 227 ms 355232 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 229 ms 355348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 346 ms 355472 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 282 ms 355376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 277 ms 355352 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 266 ms 355268 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 322 ms 355344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 287 ms 355360 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 307 ms 355272 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 295 ms 355300 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 289 ms 355420 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 308 ms 355256 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 315 ms 355476 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 322 ms 355356 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 300 ms 355268 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 328 ms 355352 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 295 ms 355336 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 249 ms 355272 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 242 ms 355244 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 320 ms 355480 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 360 ms 355344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 281 ms 355276 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 308 ms 355324 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 349 ms 355448 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 325 ms 355352 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 315 ms 355356 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 313 ms 355308 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 298 ms 355244 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 331 ms 355352 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 315 ms 355304 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 336 ms 355356 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 301 ms 355276 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 329 ms 355424 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 297 ms 355252 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 265 ms 357816 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 255 ms 357904 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 624 ms 378900 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 427 ms 358748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 308 ms 357796 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 582 ms 366468 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 629 ms 378412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 650 ms 378388 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 629 ms 378412 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 597 ms 378404 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 588 ms 378408 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 619 ms 378400 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 270 ms 355328 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 414 ms 355488 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 257 ms 355600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 255 ms 355404 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 217 ms 355276 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 224 ms 355316 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 259 ms 355524 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 247 ms 374656 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 276 ms 378372 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 275 ms 379812 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 254 ms 379780 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 223 ms 355200 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 240 ms 355276 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 325 ms 355432 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 311 ms 355416 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 246 ms 355284 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 258 ms 355244 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 356 ms 355520 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 294 ms 355248 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 274 ms 355352 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 278 ms 355260 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 269 ms 355228 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 278 ms 355376 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 276 ms 355264 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 293 ms 355352 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 282 ms 355436 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 270 ms 355344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 273 ms 355320 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 253 ms 357892 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 225 ms 357836 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 632 ms 378896 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 456 ms 358844 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 286 ms 358004 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 520 ms 366432 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 601 ms 378504 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 621 ms 378372 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 727 ms 378400 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 698 ms 378396 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 656 ms 378392 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 670 ms 378392 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1623 ms 706320 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 377 ms 355416 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 1034 ms 381436 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 364 ms 379804 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 274 ms 355356 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1299 ms 477860 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1360 ms 706404 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 1336 ms 706276 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 1226 ms 706508 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 1341 ms 706392 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 1278 ms 706400 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 1287 ms 706440 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 1219 ms 683028 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 1265 ms 706508 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'