Submission #936046

#	Time	Username	Problem	Language	Result	Execution time	Memory
936046		Populus_euphratica	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	153 ms	29792 KiB

tabletennis

#include <bits/stdc++.h>
#define int long long
using namespace std;

template<typename T> inline void read(T &x)
{
    x = 0;
    T f = 1;char ch = getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f = -1,ch = getchar();
            break;
        }
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
        x = (x<<3)+(x<<1)+ch-48,ch = getchar();
    x*=f;
}
template<typename T = int> inline T read()
{
    T x;read(x);return x;
}
template<typename T> void write(T x)
{
    if(x<0) x = -x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+48);
}
template<typename T> inline void writen(T x)
{
    write(x);
    putchar(10);
}
const int N = 2e5+5;
unordered_map<int,int> mp;
int n,k,a[N];
bool vis[N];
void solve(int sum)
{
    int l = 1,r = n+k,kpr = 0,kg = 0;
    for(int i = 1;i<=n+k;i++)
        vis[i] = 0;
    while(l<r)
    {
        if((a[l]+a[r])<sum) l++,kpr++;
        else
        {
            if((a[l]+a[r])==sum) vis[l] = vis[r] = 1,l++,r--,kg+=2;
            else if((a[l]+a[r])>sum) r--,kpr++;
        }
        if(kpr>k) return;
        if(kg==n)
        {
            for(int i = 1;i<=n+k;i++)
                if(vis[i]) cout<<a[i]<<" ";
            exit(0);
        }
    }
}
signed main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    read(n),read(k);
    for(int i = 1;i<=n+k;i++)
        read(a[i]);
    for(int i = 1;i<=2*k+1;i++)
        for(int j = max(n-k,i+1);j<=n+k;j++)
            mp[a[i]+a[j]]++;
    if((n+k)<=4*k) for(auto i:mp) solve(i.first);
    else for(auto i:mp) if(i.second>=k) solve(i.first);
    return 0;
}

• 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