Submission #447529

#	Time	Username	Problem	Language	Result	Execution time	Memory
447529		raid	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	430 ms	32440 KiB

tabletennis

#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 / 11
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 9 / 9
• Subtask 6: 14 / 14
• Subtask 7: 15 / 15
• Subtask 8: 13 / 13