Submission #525068

#	Time	Username	Problem	Language	Result	Execution time	Memory
525068		iskhakkutbilim	Table Tennis (info1cup20_tabletennis)	C++14	72 / 100	3109 ms	608756 KiB

tabletennis

// Author: Tazhibaev Iskhak
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
 
using namespace __gnu_pbds;
using namespace std;
 
typedef tree<pair<int, int> ,null_type,less< pair<int, int> >,rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const long double pi = acos((long double) - 1.0);
const double eps = (double)1e-9;
const int INF = 1e9 + 7;
    #define ff         first
    #define ss         second
    #define ll         long long
    #define ld		   long double
    #define pb         push_back
void usaco( string filename){
  freopen((filename+".in").c_str(), "r", stdin);
  freopen((filename+".out").c_str(), "w", stdout);
}
 
 
 
 
main(){
	 ios_base::sync_with_stdio(false);
	 cin.tie(nullptr); cout.tie(nullptr);
	 int n, k; cin >> n >> k;
	 vector<int> a(n + k);
	 for(int i = 0;i < n + k; i++){
	 	cin >> a[i];
	 }
	 
	 function <bool(vector<int>) > good = [&](vector<int> s){
	 	for(int i = 0;i < n; i++){
	 		int j = i + 1;
	 		if(j >= n or (n - i - 1) < 0 or (n - j - 1) < 0) break;
	 		if(s[i] + s[n-i-1] != s[j] + s[n-j-1]) return false;
	 	}
	 	return true;
	 };
	 if(k == 1){
		 int l = 1, r = n + k-1;
		 int sum = a[l] + a[r];
		int joop = 0;
		while(r > l){
			if(sum != a[r] + a[l]){
				joop = 1;
				break;
			}
			l++, r--;
		}
		if(joop == 0){
			vector<int> jp;	
			for(int i = 1;i < n + k; i++){
				jp.push_back(a[i]);
			}
			if((int)jp.size() != n) assert(false);
			for(auto x : jp){
				cout << x << " ";
			}
			return 0;
		}
		l = 0, r = n + k-2;
		sum = a[l] + a[r];
		joop = 0;
		while(r > l){
			if(sum != a[r] + a[l]){
				joop = 1;
				break;
			}
			l++, r--;
		}
		if(joop == 0){
			vector<int> jp;	
			for(int i = 0;i < n + k-1; i++){
				jp.push_back(a[i]);
			}
			if((int)jp.size() != n) assert(false);
			for(auto x : jp){
				cout << x << " ";
			}
			return 0;
		}
		sum = a[0] + a[n+k-1];
		vector<int> jp;
		multiset<int> st(a.begin(), a.end());	
		for(int i = 0;i < n + k; i++){
			if(st.count(sum - a[i]) and st.count(a[i]) and jp.size() < n){
				jp.push_back(a[i]);
				jp.push_back(sum - a[i]);
				st.erase(st.find(a[i]));
				st.erase(st.find(sum - a[i]));
			}
		}

		sort(jp.begin(), jp.end());
		 if((int)jp.size() != n) assert(false);
		 for(auto x : jp){
			 cout << x << " ";
		 }
	 }else if(n + k <= 18){
	 	for(int mask = 0; mask < (1 << (n + k)); mask++){
	 		if(__builtin_popcount(mask) != n) continue;
	 		vector<int> sub;
	 		for(int i = 0;i < n + k; i++){
	 			if(mask & (1 << i)) sub.push_back(a[i]);
	 		}
	 		if(good(sub)){
	 			for(auto x : sub) cout << x << " ";
	 			return 0;
	 		}
	 	}
	 }else if(n <= 100 and k <= 100 or (n <= 150000 and k==2)){
	 	for(int i = 0; i < n + k; i++){
	 		vector<int> sub;
	 		for(int j = i;j < n + k; j++){
	 			if(sub.size() == n) break;
	 			sub.push_back(a[j]);
	 		}
	 		if(sub.size() < n) break;
	 		if(good(sub)){
		 		for(auto x : sub){
		 			cout << x << " ";
		 		}
		 		return 0;
	 		}
	 		// cout << "\n" << "------" << "\n";
	 	}
	 }else{
		 // 1 2 3 4
	 	vector<int> jp;
		map<int, int> mp;
		for(int i = 0;i < n + k; i++){
			for(int j = i + 1; j < n + k; j++){
				mp[a[i] + a[j]]++;
			}
		}	
		int count_sum=-1, sum=-1;
		for(auto to : mp){
			if(to.ss > count_sum){
				count_sum = to.ss;
				sum = to.ff;
			}
		}
		multiset<int> st(a.begin(), a.end());	
		for(int i = 0;i < n + k; i++){
			if(st.count(sum - a[i]) and st.count(a[i]) and jp.size() < n){
				jp.push_back(a[i]);
				jp.push_back(sum - a[i]);
				st.erase(st.find(a[i]));
				st.erase(st.find(sum - a[i]));
			}
		}

		sort(jp.begin(), jp.end());
		 if((int)jp.size() != n) assert(false);
		 for(auto x : jp){
			 cout << x << " ";
		 }
	 }
    return 0;
}

Compilation message (stderr)

tabletennis.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main(){
      | ^~~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:91:61: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |    if(st.count(sum - a[i]) and st.count(a[i]) and jp.size() < n){
      |                                                   ~~~~~~~~~~^~~
tabletennis.cpp:116:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  116 |   }else if(n <= 100 and k <= 100 or (n <= 150000 and k==2)){
      |            ~~~~~~~~~^~~~~~~~~~~~
tabletennis.cpp:120:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |      if(sub.size() == n) break;
      |         ~~~~~~~~~~~^~~~
tabletennis.cpp:123:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |     if(sub.size() < n) break;
      |        ~~~~~~~~~~~^~~
tabletennis.cpp:150:61: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |    if(st.count(sum - a[i]) and st.count(a[i]) and jp.size() < n){
      |                                                   ~~~~~~~~~~^~~
tabletennis.cpp: In function 'void usaco(std::string)':
tabletennis.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen((filename+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tabletennis.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen((filename+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 15
• Subtask 8: 0 / 13