# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
687537 | vlad_TT | Table Tennis (info1cup20_tabletennis) | C++17 | 3097 ms | 22632 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///solutie rares+vlad
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <set>
using namespace std;
long long v[150405];
unordered_map <long long,long long> f;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k,suma;
cin>>n>>k;
for(int i=1;i<=n+k;i++)
{
cin>>v[i];
f[v[i]]+=1;
}
if (n + k <= 18) {
for (int mask = 1; mask < (1 << (n + k)); mask++) {
if (__builtin_popcount(mask) == n) {
vector<int> pos;
for (int bit = 0; bit < n + k; bit++) {
if (mask & (1 << bit)) pos.push_back(v[bit + 1]);
}
bool ok = 1;
for (int i = 1; i < (n / 2); i++) {
if (pos[i] + pos[n - i - 1] != pos[0] + pos[n - 1]) {
ok = false;
}
}
if (ok) {
for (auto &it : pos) {
cout << it << " ";
}
return 0;
}
}
}
}
if(k==1) {
///cazul in care nu eliminam nici 1, nici n+k
///sort(v+1,v+k+n);
suma=v[1]+v[n+k];
int eliminat,cnteliminat=0;
///cout<<"suma="<<suma<<"\n";
for(int i=2;i<n+k;i++)
{
if(f[suma-v[i]]==0||v[i]*2==suma)
{
cnteliminat++;
///cout<<"nu merge "<<v[i]<<"\n";
eliminat=v[i];
}
}
if(cnteliminat==1)
{
for(int i=1;i<=n+k;i++)
{
if(f[suma-v[i]]==1&&v[i]*2!=suma)
cout<<v[i]<<" ";
}
}
else
{
///eliminam pe primul numar
cnteliminat=0;
suma=v[2]+v[n+k];
for(int i=2;i<n+k;i++)
{
if(f[suma-v[i]]==0||v[i]*2==suma)
{
cnteliminat++;
///cout<<"nu merge "<<v[i]<<"\n";
eliminat=v[i];
}
}
if(cnteliminat==0)
{
for(int i=2;i<=n+k;i++)
cout<<v[i]<<" ";
}
else
{
for(int i=1;i<n+k;i++)
cout<<v[i]<<" ";
}
}
return 0;
}
auto dumb_cnt = [&](vector<int> v) {
int cnt = 0;
set<int> s;
int sum = v[0] + v.back();
for (auto &it : v) {
s.insert(it);
}
for (auto &it : v) {
cnt += s.count(sum - it);
}
return cnt / 2;
};
for (int i = 1; i <= n + k; i++) {
for (int j = 1; j < i; j++) {
vector<int> a;
set<int> s;
for (int k = j; k <= i; k++) {
a.push_back(v[k]);
s.insert(v[k]);
}
if (dumb_cnt(a) >= n / 2) {
int p = 0, sum = a[0] + a.back();
vector<int> output;
int aux = (n / 2);
while (aux > 0) {
if (s.count(sum - a[p])) {
aux--;
output.push_back(a[p]);
output.push_back(sum - a[p]);
}
p++;
}
sort(output.begin(), output.end());
for (auto it : output) cout << it << " ";
return 0;
}
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |