Submission #423610

#	Time	Username	Problem	Language	Result	Execution time	Memory
423610		tqbfjotld	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	336 ms	10900 KiB

tabletennis

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

vector<int> stuff;

bool can(int l, int r, int goal, int tot){
    if (goal==0) return true;
    if (goal>(r-l+1)/2) return false;
    if (tot-stuff[l]<=stuff[l]) return false;
    int lb = lower_bound(stuff.begin(),stuff.end(),tot-stuff[l])-stuff.begin();
    if (lb!=stuff.size() && stuff[lb]==tot-stuff[l]){
        return can(l+1,lb-1,goal-1,tot);
    }
    else{
        return can(l+1,lb-1,goal,tot);
    }
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for (int x = 0; x<n+k; x++){
        int t;
        scanf("%d",&t);
        stuff.push_back(t);
    }
    int foundtot = -1;
    for (int l = 0; l<=k; l++){
        for (int r = n+k-1; r>=n-1; r--){
            if (can(l,r,n/2,stuff[l]+stuff[r])){
                foundtot = stuff[l]+stuff[r];
                break;
            }
        }
        if (foundtot!=-1) break;
    }
    set<int> ans;
    for (int x = 0; x<n+k; x++){
        if (ans.size()==n) break;
        int lb = lower_bound(stuff.begin(),stuff.end(),foundtot-stuff[x])-stuff.begin();
        if (lb!=stuff.size() && stuff[lb]==foundtot-stuff[x]){
            ans.insert(stuff[x]);
            ans.insert(foundtot-stuff[x]);
        }
    }
    for (auto x : ans){
        printf("%d ",x);
    }
}

Compilation message (stderr)

tabletennis.cpp: In function 'bool can(int, int, int, int)':
tabletennis.cpp:11:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if (lb!=stuff.size() && stuff[lb]==tot-stuff[l]){
      |         ~~^~~~~~~~~~~~~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:39:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |         if (ans.size()==n) break;
      |             ~~~~~~~~~~^~~
tabletennis.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if (lb!=stuff.size() && stuff[lb]==foundtot-stuff[x]){
      |             ~~^~~~~~~~~~~~~~
tabletennis.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
tabletennis.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~

• 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