oj.uz

Submission #423646

# Submission time Handle Problem Language Result Execution time Memory
423646 2021-06-11T10:52:06 Z errorgorn Table Tennis (info1cup20_tabletennis) C++17
87 / 100
 3000 ms 411028 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#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 rep(x,s,e) for (auto x=s;x!=e;x++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

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

int n,k;
int arr[160005];
vector<int> v[12345678];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,0,n+k) cin>>arr[x];
	
	int l=n,r=n+k+k;
	rep(x,0,n+k){
		l--,r--;
		
		if (r<x) break;
		
		int a=max(x+1,l),b=min(r,n+k)+1;
		rep(y,a,b){
			//cout<<x<<" "<<y<<endl;
			v[(arr[x]+arr[y])%12345678].pub(arr[x]+arr[y]);
		}
	}
	
	if (k>=400 && n>=50000) return 0;
	
	int val;
	
	rep(x,0,12345678) if (!v[x].empty()){
		sort(all(v[x]));
		int curr=-1;
		int cnt=0;
		for (auto it:v[x]){
			if (it!=curr) curr=it,cnt=0;
			cnt++;
			
			if (cnt>=n/2){
				val=curr;
			}
		}
	}
	
	vector<int> ans;
	
	r=n+k-1;
	rep(x,0,n+k){
		while (arr[x]+arr[r]>val) r--;
		if (arr[x]+arr[r]==val){
			ans.pub(arr[x]);
			ans.pub(arr[r]);
			r--;
			
			if (sz(ans)==n) break;
		}
	}
	
	sort(all(ans));
	
	for (auto &it:ans) cout<<it<<" "; cout<<endl;
}

Compilation message

tabletennis.cpp: In function 'int main()':
tabletennis.cpp:80:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |  for (auto &it:ans) cout<<it<<" "; cout<<endl;
      |  ^~~
tabletennis.cpp:80:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |  for (auto &it:ans) cout<<it<<" "; cout<<endl;
      |                                    ^~~~
tabletennis.cpp:69:3: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |   if (arr[x]+arr[r]==val){
      |   ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 290244 KB Output is correct
2 Correct 189 ms 290216 KB Output is correct
3 Correct 186 ms 290272 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 290792 KB Output is correct
2 Correct 241 ms 294548 KB Output is correct
3 Correct 239 ms 294532 KB Output is correct
4 Correct 234 ms 294556 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 294756 KB Output is correct
2 Correct 241 ms 295088 KB Output is correct
3 Correct 236 ms 294876 KB Output is correct
4 Correct 230 ms 295056 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 290492 KB Output is correct
2 Correct 186 ms 290512 KB Output is correct
3 Correct 197 ms 290660 KB Output is correct
4 Correct 188 ms 290628 KB Output is correct
5 Correct 189 ms 290668 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 290116 KB Output is correct
2 Correct 193 ms 290140 KB Output is correct
3 Correct 184 ms 290320 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 290272 KB Output is correct
2 Correct 199 ms 290372 KB Output is correct
3 Correct 192 ms 291268 KB Output is correct
4 Correct 185 ms 290592 KB Output is correct
5 Correct 189 ms 290408 KB Output is correct
6 Correct 184 ms 290368 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 290116 KB Output is correct
2 Correct 666 ms 316252 KB Output is correct
3 Correct 433 ms 313524 KB Output is correct
4 Correct 345 ms 308580 KB Output is correct
5 Correct 384 ms 313500 KB Output is correct
6 Correct 342 ms 306596 KB Output is correct
7 Correct 329 ms 308512 KB Output is correct
8 Correct 331 ms 307868 KB Output is correct

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 293100 KB Output is correct
2 Execution timed out 3079 ms 411028 KB Time limit exceeded
3 Halted 0 ms 0 KB -