oj.uz

Submission #447529

# Submission time Handle Problem Language Result Execution time Memory
447529 2021-07-26T16:24:02 Z raid Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 430 ms 32440 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;
    }
    sol.clear();
  }
  sort( sol.begin(), sol.end() );
  for ( int i = 0; i < (int)sol.size(); ++i ) {
	  cout << sol[i] << " ";
  }
  return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 720 KB Output is correct
2 Correct 97 ms 3080 KB Output is correct
3 Correct 94 ms 2976 KB Output is correct
4 Correct 96 ms 3068 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3000 KB Output is correct
2 Correct 96 ms 3072 KB Output is correct
3 Correct 100 ms 2996 KB Output is correct
4 Correct 94 ms 3256 KB Output is correct

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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 97 ms 3060 KB Output is correct
3 Correct 93 ms 3020 KB Output is correct
4 Correct 98 ms 3096 KB Output is correct
5 Correct 96 ms 3072 KB Output is correct
6 Correct 98 ms 3092 KB Output is correct
7 Correct 100 ms 3036 KB Output is correct
8 Correct 100 ms 3064 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4540 KB Output is correct
2 Correct 430 ms 30728 KB Output is correct
3 Correct 371 ms 32440 KB Output is correct
4 Correct 291 ms 28320 KB Output is correct
5 Correct 156 ms 9992 KB Output is correct
6 Correct 124 ms 3380 KB Output is correct
7 Correct 277 ms 25104 KB Output is correct
8 Correct 268 ms 27452 KB Output is correct