oj.uz

Submission #523352

# Submission time Handle Problem Language Result Execution time Memory
523352 2022-02-07T14:18:51 Z Ahmed2me Table Tennis (info1cup20_tabletennis) C++17
0 / 100
 19 ms 1488 KB 
#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;
    ll cnt=false;
    while(i<j)
    {
        if(a[i]+a[j]==sum){cnt++;i++;j--;continue;}
        if(a[i]+a[j]>sum){j--;continue;}
        if(a[i]+a[j]<sum){i++;continue;}
    }
    return cnt>=(n/2);
}

void print_ans(ll sum)
{
    ll i=1;
    ll j=n;
    while(i<j)
    {
        if(a[i]+a[j]==sum){cout<<a[i]<<sp<<a[j]<<sp;i++;j--;continue;}
        if(a[i]+a[j]>sum){j--;continue;}
        if(a[i]+a[j]<sum){i++;continue;}
    }
    return;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){cin>>a[i];}
    set<int>st;sort(a+1,a+n+1);
    for(int i=1;i<=2*m;i++)
    {
        for(int j=(n+m)-2*m+1;j<=n+m;j++)
        {
            st.insert(a[i]+a[j]);
        }
    }
    for(auto I:st){if(good(I)){print_ans(I);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

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1488 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output not sorted
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output not sorted
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output not sorted
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output not sorted
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 488 KB Output not sorted
2 Halted 0 ms 0 KB -