Submission #888300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888300	2023-12-16T21:45:50 Z	raul2008487	Table Tennis (info1cup20_tabletennis)	C++17	58 / 100	3000 ms	7560 KB

tabletennis

/// R
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define in insert
#define mpr make_pair
#define vl vector<ll>
#define endl '\n'
using namespace std;
const int sz = 2e5+5;
const ll inf = 1000000000000000;
//tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;a
/*struct DSU{
    vector<ll> e;
    void init(ll n){
        e.assign(n+1, -1);
    }
    ll base(ll x){
        if(e[x] < 0){
            return x;
        }
        return e[x] = base(e[x]);
    }
    bool unite(ll a, ll b){
        a = base(a);
        b = base(b);
        if(a == b){return false;}
        if(e[a] > e[b]){
            swap(a, b);
        }
        e[a] += e[b];
        e[b] = a;
        return true;
    }
};*/
ll n, k, m;
void print(vl v){
    for(auto x: v){
        cout << x << ' ';
    }
    cout << endl;
}
void solve(){
    ll i, j, bg, ed, pt, w1, w2, cnt, l, r, cc;
    cin>>n>>k;
    m = n + k;
    vl d, v(m), res;
    for(i=0;i<m;i++){
        cin>>v[i];
    }
    for(i=1;i<m;i++){
        d.pb(v[i] - v[i-1]);
    }
    for(i=0;i<=k;i++){
        for(j=0;j<=k-i;j++){
            bg = i;
            ed = m - 2 - j;
            cc = i + j;
            bool as = 0, tmr = 1;
            w1 = 0, w2 = 0;
            if(bg > ed){
                continue;
            }
            vl bad;
            w1 = d[bg];
            w2 = d[ed];
            cnt = 1;
            while(bg < ed){
                if(w1 == w2){
                    cnt++;
                    bg++;ed--;
                    w1 = d[bg];
                    w2 = d[ed];
                    tmr = 1;
                    continue;
                }
                else if(w1 > w2){
                    bad.pb(ed);
                    ed--;
                    cc++;
                    w2 += d[ed];
                }
                else{
                    bg++;
                    cc++;
                    bad.pb(bg);
                    w1 += d[bg];
                }
                tmr = 0;
            }
            //if(cc > k){continue;}
            if(tmr && cnt >= (n/2)){
                l = i;
                r = m - j - 1;
                ll p = 0;
                for(pt = l; pt <= r; pt++){
                    if(p < bad.size() && pt == bad[p]){p++;continue;}
                    res.pb(v[pt]);
                }
                print(res);
                return ;
            }
        }
    }
    assert(0);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}
/*
6 3
1 2 3 6 7 9 10 12 14
 
 
1 3 6 7 10 12
*/

Compilation message

tabletennis.cpp: In function 'void solve()':
tabletennis.cpp:100:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                     if(p < bad.size() && pt == bad[p]){p++;continue;}
      |                        ~~^~~~~~~~~~~~
tabletennis.cpp:62:18: warning: unused variable 'as' [-Wunused-variable]
   62 |             bool as = 0, tmr = 1;
      |                  ^~

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1372 KB	Output is correct
2	Correct	25 ms	7460 KB	Output is correct
3	Correct	23 ms	7504 KB	Output is correct
4	Correct	23 ms	7352 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	7560 KB	Output is correct
2	Correct	24 ms	7348 KB	Output is correct
3	Correct	27 ms	7540 KB	Output is correct
4	Correct	24 ms	7336 KB	Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #6
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	424 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Incorrect	1 ms	348 KB	Extra information in the output file
7	Halted	0 ms	0 KB	-

Subtask #7
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	312 ms	7444 KB	Output does not have symmetry property
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Execution timed out	3039 ms	6516 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-