제출 #1346476

#제출 시각아이디문제언어결과실행 시간메모리
1346476bakhtiyarnTable Tennis (info1cup20_tabletennis)C++20
15 / 100
3101 ms360996 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

int getRandom(int l, int r) {
  static mt19937_64 gen(random_device{}());
  uniform_int_distribution<int> dis(l, r);
  return dis(gen);
}

const int N = 3e5+5;
int a[N];
int n, k; 
unordered_map<int, int> pos;

vector<int> build(int dif){
  vector<int> ans;
  vector<int> dp(n+k+1);
  vector<array<int, 2>> from(n+k+1);
  for(int i=1; i<=n+k; i++){
    dp[i] = dp[i-1];
    from[i] = {i-1, 0};
    
    if(a[i]-dif >= 1 and pos[a[i]-dif]) {
      if(dp[i] < dp[pos[a[i]-dif]-1] + 2){
        dp[i] = dp[pos[a[i]-dif]-1] + 2;
        from[i] = {pos[a[i]-dif], i};
      }
    }
  }
  
  int i = n+k;
  while(i >= 1){
    if(from[i][1] == 0){
      i--;
      continue;
    }
    ans.push_back(a[from[i][1]]);
    ans.push_back(a[from[i][0]]);
    i = from[i][0]-1;
  }
  
  return ans;
}

// for(int i=1; i<=n; i++) 
void solve(){
  cin >> n >> k;
  for(int i=1; i<=n+k; i++) cin >> a[i], pos[a[i]] = i;
  sort(a+1, a+n+k+1);
  
  for(int l=1; l<=n+k; l++){
    for(int r=l+1; r<=n+k; r++){
      int dif = a[r] - a[l];
      vector<int> ans = build(dif);
      while(ans.size() > n) ans.pop_back();
      if(ans.size() == n) {
        reverse(ans.begin(), ans.end());
        for(int i: ans) cout << i << " ";
        return;
      }
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...