oj.uz

Submission #369159

# Submission time Handle Problem Language Result Execution time Memory
369159 2021-02-20T15:37:52 Z doowey Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 952 ms 5484 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, k;
    cin >> n >> k;
    int m = (n + k);
    vector<int> q(m);
    for(int i = 0; i  < m ; i ++)
        cin >> q[i];
    sort(q.begin(), q.end());
    vector<pii> tak;
    for(int i = 0 ; i < m ; i ++ ){
        for(int j = 1; j <= k + 1; j ++ ){
            if(i + j < m && i + 1 >= n/2 && m-(i+j) >= n/2){
                tak.push_back(mp(i,i+j));
            }
        }
    }
    random_shuffle(tak.begin(), tak.end());
    int pari = 0;
    int rem = n/2;
    vector<int> soln;
    int ci, cj;
    int pi, pj;
    bool brok;
    for(auto pari : tak){
        rem = n/2-1;
        pi = pari.fi;
        pj = pari.se;
        soln.clear();
        soln.push_back(pi);
        soln.push_back(pj);
        ci = pi-1;
        cj = pj+1;
        while(rem > 0){
            if(ci < 0 || cj >= m || (ci + 1) < rem || (m-cj) < rem) break;
                if(q[pi]+q[pj] == q[ci]+q[cj]){
                    soln.push_back(ci);
                    soln.push_back(cj);
                    pi = ci;
                    pj = cj;
                    ci -- ;
                    cj ++ ;
                    rem -- ;
                }
                else{
                    if(q[ci]+q[cj] > q[pi]+q[pj]){
                        ci--;
                    }
                    else{
                        cj++;
                    }
                }
        }
        if(rem == 0){
            sort(soln.begin(), soln.end());
            for(auto x : soln)
                cout << q[x] << " ";
            cout << "\n";
            return 0;
        }
    }
    return 0;
}

Compilation message

tabletennis.cpp: In function 'int main()':
tabletennis.cpp:32:9: warning: unused variable 'pari' [-Wunused-variable]
   32 |     int pari = 0;
      |         ^~~~
tabletennis.cpp:37:10: warning: unused variable 'brok' [-Wunused-variable]
   37 |     bool brok;
      |          ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 876 KB Output is correct
2 Correct 42 ms 3176 KB Output is correct
3 Correct 42 ms 3176 KB Output is correct
4 Correct 42 ms 3176 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3304 KB Output is correct
2 Correct 42 ms 3176 KB Output is correct
3 Correct 44 ms 3176 KB Output is correct
4 Correct 52 ms 3176 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 50 ms 3172 KB Output is correct
3 Correct 47 ms 3172 KB Output is correct
4 Correct 63 ms 3108 KB Output is correct
5 Correct 52 ms 3172 KB Output is correct
6 Correct 48 ms 3172 KB Output is correct
7 Correct 47 ms 3172 KB Output is correct
8 Correct 54 ms 3100 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1564 KB Output is correct
2 Correct 132 ms 3820 KB Output is correct
3 Correct 213 ms 5356 KB Output is correct
4 Correct 135 ms 5356 KB Output is correct
5 Correct 952 ms 5320 KB Output is correct
6 Correct 114 ms 5228 KB Output is correct
7 Correct 210 ms 5228 KB Output is correct
8 Correct 212 ms 5484 KB Output is correct