Submission #523408

#	Time	Username	Problem	Language	Result	Execution time	Memory
523408		Ahmed2me	Table Tennis (info1cup20_tabletennis)	C++17	34 / 100	119 ms	10100 KiB

tabletennis

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ll long long
#define fl cout.flush();
#define endl '\n'
#define sp ' '

using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

inline void fileim(bool usaco,bool cs,bool cs2,char *s,char *s2)
{
    if(usaco)
    {
        #define fin cin
        #define fout cout
    }
    if(cs){freopen( s, "r", stdin );}
    if(cs2){freopen( s2, "w", stdout );}
}

const int mxint = 2147483647 ;
const ll MOD=1e9+7;
const ll N=3e6;
const double EPS=1e-6;

vector<int>pr;int lp[1000001];

ll power(ll x, ll y)
{
    ll ans=1;while(y){if(y&1){ ans=(ans*x)%MOD; }y/=2;x=(x*x)%MOD;}return ans;
}

ll bitcount(ll num){ ll rtrn=0;while(num){rtrn++;num=(num&(num-1));}return rtrn; }
ll inv(ll x){return power(x , MOD-2);}

void linear_seive()
{
    for(int i=2;i<=N;i++)
    {
        if(!lp[i]){lp[i]=i;pr.push_back(i);}
        for(int j=0;j<pr.size()&&pr[j]<=lp[i]&&i*pr[j]<=N;j++){lp[i*pr[j]]=pr[j];}
    }
}

ll t=1,n,m,a[200020];

bool good(ll sum)
{
    ll i=1,j=n+m;
    ll cnt=false;
    while(i<j)
    {
        if(cnt>=n){return true;}
        if(a[i]+a[j]==sum){cnt+=2;i++;j--;continue;}
        if(a[i]+a[j]>sum){j--;continue;}
        if(a[i]+a[j]<sum){i++;continue;}
    }
    return cnt>=(n);
}

void print_ans(ll sum)
{
    ll i=1;ll j=n+m;
    ll cnt=false;
    set<ll>ans;
    while(i<j)
    {
        if(cnt>=n){break;}
        if(a[i]+a[j]==sum){cnt+=2;ans.insert(a[i]);ans.insert(a[j]);i++;j--;continue;}
        if(a[i]+a[j]>sum){j--;continue;}
        if(a[i]+a[j]<sum){i++;continue;}
    }
    for(auto I:ans){cout<<I<<sp;}
    return;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n+m;i++){cin>>a[i];}
    map<int,int>mp;sort(a+1,a+n+m+1);
    for(int i=1;i<=min(n,2*m);i++)
    {
        for(int j=max(1ll,(n+m)-2*m+1);j<=n+m;j++)
        {
            mp[(a[i]+a[j])]++;
        }
    }
    for(auto I:mp){if(I.second>=m&&good(I.first)){print_ans(I.first);return;}}
}

int main()
{
    //ios::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    //cin>>t;//linear_seive();//fileim( 1,1,1, "hps.in","hps.out" );
    //cout<< fixed << setprecision(15) ;
    while(t--){solve();}return 0;
}

Compilation message (stderr)

tabletennis.cpp: In function 'void linear_seive()':
tabletennis.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0;j<pr.size()&&pr[j]<=lp[i]&&i*pr[j]<=N;j++){lp[i*pr[j]]=pr[j];}
      |                     ~^~~~~~~~~~

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