Submission #864395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864395	2023-10-22T17:31:12 Z	NotLinux	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	1694 ms	56952 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int n,arr[N];
map < int , int > dp;
int calc(int x){
	if(x & 1)return 1;
	else if(dp.count(x))return dp[x];
	else return dp[x] = calc(x/2) * 2;
}
void search(int len ,int cur , int tar){
	if(len & 1){
		cout << len << endl;
	}
	else if((calc(len/2) + cur) < tar){//sağ tarafa
		search(len/2 , cur + calc(len/2) , tar);
	}
	else{//sol tarafa
		search(len/2 , cur + calc(len/2) , tar);
	}
}
void solve(){
	cin >> n;
	for(int i = 0;i<n;i++)cin >> arr[i];
	int pre[n+1];
	memset(pre , 0, sizeof(pre));
	for(int i = 0;i<n;i++){
		pre[i+1] = pre[i] + calc(arr[i]);
	}
	int q;cin >> q;
	while(q--){
		int x;cin >> x;
		int l = 0 , r = n;
		while(l < r){
			int mid = (l+r)/2;
			if(pre[mid] >= x)r = mid;
			else l = mid+1;
		}
		l--;//küçük olan son yer
		search(arr[l] , pre[l-1] , x);
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	56 ms	4136 KB	Output is correct
4	Correct	187 ms	2364 KB	Output is correct
5	Correct	252 ms	5456 KB	Output is correct
6	Correct	141 ms	4152 KB	Output is correct
7	Correct	256 ms	5456 KB	Output is correct
8	Correct	268 ms	5716 KB	Output is correct

Subtask #2

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	6 ms	860 KB	Output is correct
12	Correct	3 ms	348 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	5 ms	860 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	56 ms	4136 KB	Output is correct
4	Correct	187 ms	2364 KB	Output is correct
5	Correct	252 ms	5456 KB	Output is correct
6	Correct	141 ms	4152 KB	Output is correct
7	Correct	256 ms	5456 KB	Output is correct
8	Correct	268 ms	5716 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	2 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	604 KB	Output is correct
19	Correct	6 ms	860 KB	Output is correct
20	Correct	3 ms	348 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	5 ms	860 KB	Output is correct
23	Correct	185 ms	5472 KB	Output is correct
24	Correct	182 ms	14124 KB	Output is correct
25	Correct	379 ms	21328 KB	Output is correct
26	Correct	944 ms	39124 KB	Output is correct
27	Correct	882 ms	42628 KB	Output is correct
28	Correct	1694 ms	56952 KB	Output is correct
29	Correct	471 ms	8836 KB	Output is correct
30	Correct	546 ms	10024 KB	Output is correct
31	Correct	1380 ms	43680 KB	Output is correct