oj.uz

Submission #638682

# Submission time Handle Problem Language Result Execution time Memory
638682 2022-09-06T18:56:36 Z Dec0Dedd Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 487 ms 45612 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
const int N = 2e5+10;
const int K = 400;
 
int a[N], n, k, sz;
gp_hash_table<int, bool> m;

int num(int s) {
   int res=0;
   for (int i=1; i<=sz; ++i) {
      if (2*a[i] == s || m.find(s-a[i]) == m.end()) continue;
      ++res;
   }
   return res;
}

vector<int> gen(int s) {
   vector<int> res; int p=0;
   for (int i=1; i<=sz; ++i) {
      if (2*a[i] == s || m.find(s-a[i]) == m.end()) continue;
      res.push_back(a[i]), res.push_back(s-a[i]);
      p+=2;
      if (p == n) break;
   }
   return res;
}
 
int main() {
 
   cin>>n>>k;
   sz=n+k;
   for (int i=1; i<=sz; ++i) cin>>a[i];
   for (int i=1; i<=sz; ++i) m[a[i]]=true;

   vector<int> x;

   if (sz <= 5*K) {
      bool ok=false;
      for (int i=1; i<=sz && !ok; ++i) {
         for (int j=i+1; j<=sz && !ok; ++j) {
            if (num(a[i]+a[j]) >= n) {
               x=gen(a[i]+a[j]);
               ok=true;
               break;
            }
         }
      }
   } else {
      gp_hash_table<int, int> cnt;

      for (int i=1; i<=2*k+1; ++i) {
         for (int j=n-k-1; j<=sz; ++j) ++cnt[a[i]+a[j]];
      }

      for (auto u : cnt) {
         if (u.second >= k) {
            if (num(u.first) >= n) {
               x=gen(u.first);
               break;
            }
         }
      }
   }

   sort(x.begin(), x.end());
   assert((int)x.size() >= n);
   for (auto u : x) cout<<u<<" ";
   cout<<"\n";
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1740 KB Output is correct
2 Correct 97 ms 11604 KB Output is correct
3 Correct 104 ms 11584 KB Output is correct
4 Correct 105 ms 11604 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 11492 KB Output is correct
2 Correct 101 ms 11536 KB Output is correct
3 Correct 96 ms 11616 KB Output is correct
4 Correct 105 ms 11520 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 23 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 304 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 102 ms 11508 KB Output is correct
3 Correct 98 ms 11568 KB Output is correct
4 Correct 103 ms 11516 KB Output is correct
5 Correct 165 ms 11584 KB Output is correct
6 Correct 82 ms 11636 KB Output is correct
7 Correct 94 ms 11732 KB Output is correct
8 Correct 103 ms 11584 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 164 ms 45612 KB Output is correct
3 Correct 159 ms 45536 KB Output is correct
4 Correct 266 ms 45520 KB Output is correct
5 Correct 487 ms 19252 KB Output is correct
6 Correct 88 ms 11528 KB Output is correct
7 Correct 427 ms 28552 KB Output is correct
8 Correct 131 ms 28572 KB Output is correct