Submission #638124

#	Time	Username	Problem	Language	Result	Execution time	Memory
638124		Dec0Dedd	Table Tennis (info1cup20_tabletennis)	C++14	0 / 100	3062 ms	36360 KiB

tabletennis

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+1;

vector<int> v;
int a[N], n, k, sz;

int lgap(int r) {
   map<int, vector<int>> mp;
   for (int i=1; i<=sz; ++i) mp[a[i]%r].push_back(a[i]);

   vector<int> mv;
   for (auto u : mp) {
      vector<int> res;

      int sz=u.second.size();
      res.push_back(u.second[0]);
      for (int i=1; i<sz; ++i) {
         if (u.second[i]-res.back() != r) {
            if (res.size() >= mv.size()) mv.swap(res), res.clear();
         }
         res.push_back(u.second[i]);
      }

      if (res.size() >= mv.size()) mv.swap(res);
   }
   v.swap(mv);

   return v.size();
}

int main() {
   cin>>n>>k;
   sz=n+k;
   for (int i=1; i<=sz; ++i) cin>>a[i];
   sort(a+1, a+sz+1);

   if (n <= k) {
      bool ok=false;
      for (int i=1; i<=sz && !ok; ++i) {
         for (int j=i+1; j<=sz && !ok; ++j) {
            if (lgap(a[j]-a[i]) >= n) ok=true;
         }
      }
      assert(ok);
   } else if (n <= 2e3) {
      bool ok=false;
      for (int i=1; i<sz; ++i) {
         if (lgap(a[i+1]-a[i]) >= n) {
            ok=true;
            break;
         } 
      }
      assert(ok);
   } else {
      map<int, int> cnt;
      for (int i=1; i<sz; ++i) ++cnt[a[i+1]-a[i]];

      int x=0, r=0;
      for (auto u : cnt) {
         if (u.second > x) r=u.first;
      }

      assert(lgap(r) >= n);
   }
   
   assert((int)v.size() >= n);
   for (int i=0; i<n; ++i) cout<<v[i]<<" ";
   cout<<"\n";
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13