Submission #1062234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062234		pera	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	148 ms	3188 KiB

tabletennis

#include<bits/stdc++.h>
using namespace std;
const int TL = 8e7;
int main(){
   srand(time(0));
   int n , k;
   cin >> n >> k;
   vector<int> a(n + k + 1);
   for(int i = 1;i <= n + k;i ++){
      cin >> a[i];
   }
   auto Check = [&](int sum){
      vector<int> ans; 
      int l = 1 , r = n + k;
      while(l < r && (int)ans.size() < n && (int)ans.size() + r - l + 1 >= n){
         int val = a[l] + a[r];
         if(val == sum){
            ans.emplace_back(l++);
            ans.emplace_back(r--);
         }else if(val > sum){
            --r;
         }else{
            ++l;
         }
      }
      if((int)ans.size() == n){
         sort(ans.begin() , ans.end());
         for(int i = 0;i < n;i ++){
            cout << a[ans[i]] << " ";
         }
         cout << endl;
         exit(0);
      }
   };
   if(n * k * k < TL){
      for(int x = 1;x <= k + 1;x ++){
         for(int y = n - 1;y <= n + k;y ++){
            Check(a[x] + a[y]);
         }
      }
   }
   for(int x = 1;x <= 200;x ++){
      int u = rand() % (n + k) + 1;
      int v = rand() % (n + k) + 1;
      if(u != v){
         Check(a[u] + a[v]);
      }
   }
}

• 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