oj.uz

답안 #423610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423610 2021-06-11T10:22:26 Z tqbfjotld Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 336 ms 10900 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 392 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1516 KB Output is correct
2 Correct 91 ms 9376 KB Output is correct
3 Correct 89 ms 9272 KB Output is correct
4 Correct 96 ms 9356 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 9332 KB Output is correct
2 Correct 97 ms 9380 KB Output is correct
3 Correct 102 ms 9328 KB Output is correct
4 Correct 92 ms 9356 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 89 ms 9364 KB Output is correct
3 Correct 90 ms 10764 KB Output is correct
4 Correct 101 ms 10900 KB Output is correct
5 Correct 101 ms 10804 KB Output is correct
6 Correct 95 ms 10816 KB Output is correct
7 Correct 93 ms 10812 KB Output is correct
8 Correct 92 ms 10844 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 336 ms 9316 KB Output is correct
3 Correct 95 ms 10768 KB Output is correct
4 Correct 288 ms 10764 KB Output is correct
5 Correct 92 ms 10736 KB Output is correct
6 Correct 98 ms 10860 KB Output is correct
7 Correct 265 ms 10740 KB Output is correct
8 Correct 93 ms 10752 KB Output is correct