oj.uz

Submission #447528

# Submission time Handle Problem Language Result Execution time Memory
447528 2021-07-26T16:22:47 Z raid Table Tennis (info1cup20_tabletennis) C++17
61 / 100
 403 ms 32360 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int MAX = 150402;

int v[MAX];
map<int, int> S;
vector<int> sol, mxs;

int main() {
  int n, k;

  cin >> n >> k;
  for ( int i = 1; i <= n + k; ++i ) {
	  cin >> v[i];
  }
  sort( v + 1, v + n + k + 1 );
  if ( n + k >= 4 * k + 3 ) { 
    for ( int i = 1; i <= 2 * k + 1; ++i ) {
	    for ( int j = n + k; j >= n - k; --j ) {
		    ++S[v[i] + v[j]];
	    }
    }
  } else {
	for ( int i = 1; i <= n + k; ++i ) {
    for ( int j = i + 1; j <= n + k; ++j ) {
		    ++S[v[i] + v[j]];
	    }
	  }
  }
  int sum = 0, mx = 0;
  for ( auto it : S ) {
    if ( mx < it.second ) {
	    mx = it.second;
	  }
  }
  for ( auto it : S ) {
    if ( it.second == mx ) {
      mxs.push_back( it.first );
    }
  }
  for ( int it = 0; it < (int)mxs.size(); ++it ) {
    int i = 1, j = n + k;
    sum = mxs[it];
    while ( i < j ) {
    	if ( sum == v[i] + v[j] ) {
    	  if ( (int)sol.size() < n ) {
    	    sol.push_back( v[i] );
    	    sol.push_back( v[j] );
    	  }
    	  ++i;
    	  --j;
    	} else if ( sum < v[i] + v[j] ) {
    	  --j;
    	} else {
    	  ++i;
    	}
    }
    if ( (int)sol.size() == n ) {
      break;
    }
  }
  sort( sol.begin(), sol.end() );
  for ( int i = 0; i < (int)sol.size(); ++i ) {
	  cout << sol[i] << " ";
  }
  return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output not subsequence of input
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 744 KB Output is correct
2 Correct 95 ms 2992 KB Output is correct
3 Correct 94 ms 2984 KB Output is correct
4 Correct 94 ms 2996 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3148 KB Output is correct
2 Correct 94 ms 3048 KB Output is correct
3 Incorrect 95 ms 3036 KB Output not subsequence of input
4 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 4 ms 972 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 288 KB Output not subsequence of input
3 Halted 0 ms 0 KB -

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 94 ms 3116 KB Output is correct
3 Correct 93 ms 3140 KB Output is correct
4 Correct 97 ms 3052 KB Output is correct
5 Correct 92 ms 3024 KB Output is correct
6 Correct 98 ms 3216 KB Output is correct
7 Correct 95 ms 3036 KB Output is correct
8 Correct 93 ms 3212 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4632 KB Output is correct
2 Correct 403 ms 30640 KB Output is correct
3 Correct 361 ms 32360 KB Output is correct
4 Correct 288 ms 28352 KB Output is correct
5 Correct 157 ms 9916 KB Output is correct
6 Correct 124 ms 3360 KB Output is correct
7 Correct 273 ms 25024 KB Output is correct
8 Correct 259 ms 27268 KB Output is correct