Submission #499561

#	Time	Username	Problem	Language	Result	Execution time	Memory
499561		bigo	Table Tennis (info1cup20_tabletennis)	C++14	0 / 100	154 ms	7876 KiB

tabletennis

#include <iostream>
#include <cmath>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#define M 1000000007
#define pii pair<int, int>
typedef long long ll;
using namespace std;
/*
vector<vector<int>>vec;
vector<bool>visit;
vector<int>w;
vector<pair<int, pii>>dp1;
vector<pair<int, pii>>dp2;
vector<int>pre;
pair<int,pii> max1(pair<int, pii>a1, pair<int, pii>a2,bool v1,bool v2) {
    if (a1.first > a2.first)
        return a1;
    else if (a1.first < a2.first)
        return a2;
    else {
        if (v1 and !v2)
            return a1;
        if (v2 and !v1)
            return a2;
        else {
            int tmp1 = abs(a1.second.second - a1.second.first);
            int tmp2 = abs(a2.second.second - a2.second.first);
            if (tmp1 > tmp2)
                return a1;
            else if (tmp2 > tmp1)
                return a2;
            else {
                if (a1.second.second > a2.second.second) {
                    return a1;
                }
                else if (a2.second.second > a1.second.second)
                    return a2;
                else {
                    if (a1.second.first > a2.second.first) {
                        return a2;
                    }
                    else if (a2.second.first > a1.second.first)
                        return a1;
                    else
                        return a1;
                }
            }
        }
    }
}
vector<bool>he;
void dfs(int v) {
    visit[v] = true;
    for (int i = 0; i < vec[v].size(); i++) {
        if (!visit[vec[v][i]]) {
            dfs(vec[v][i]);
        }
        dp2[v] = max1({ dp1[vec[v][i]].first,{w[v],w[v]} }, dp2[v], true, true);
        int val2 = abs(w[vec[v][i]] - w[v]) + dp2[vec[v][i]].first;
        int val = dp1[vec[v][i]].second.second - dp1[vec[v][i]].second.first;
        int val1 = max(dp1[vec[v][i]].second.second, w[v]) - min(dp1[vec[v][i]].second.first, w[v]);
        int val3 = dp1[vec[v][i]].first - val + val1;
        bool tmp123 = he[v];
        if (val1 > val)
            he[v] = true;
        else
            he[v] = false;
        if (val3 >= val2) {
            pair<int, pii> a1 = max1({ val3,{min(dp1[vec[v][i]].second.first, w[v]),max(dp1[vec[v][i]].second.second, w[v])} }, dp1[v], he[i], tmp123);
            if (dp1[v] != a1 )
                pre[v] = vec[v][i];
            dp1[v] = a1;
        }
        else {
            pair <int, pii>a1 = max1({ val2,{min(w[vec[v][i]],w[i]),max(w[vec[v][i]],w[i])} }, dp1[v], he[i], tmp123);
            if (dp1[v] != a1)
                pre[v] = vec[v][i];
            dp1[v] = a1;
        }
    }
}
vector<int>sed;
void bfs(int v) {
    vector<bool>visit(vec.size());
    vector<int>distance1(vec.size());
    distance1[v] = 0;
    for (int i = 0; i < vec.size(); i++) {
        visit[i] = false;
    }
    queue<int>queue1;
    queue1.push(v);
    visit[v] = true;
    while (queue1.empty() == false) {
        sed.push_back(queue1.front());
        int cur = queue1.front();
        queue1.pop();
        for (int i = 0; i < vec[cur].size(); i++) {
            if (visit[vec[cur][i]] == false) {
                visit[vec[cur][i]] = true;
                distance1[vec[cur][i]] = distance1[cur] + 1;
                queue1.push(vec[cur][i]);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    he.resize(n);
    pre.resize(n,-1);
    w.resize(n);
    for (int i = 0; i < n; i++)
        cin >> w[i];
    vec.resize(n);
    visit.resize(n, false);
    vector<int>num(n, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        vec[u].push_back(v);
        num[u]++;
    }
    dp1.resize(n, { -1,{-1,-1} });
    dp2.resize(n, { -1,{-1,-1} });
    for (int i = 0; i < n; i++) {
        if (num[i] == 0) {
            dp1[i] = { 0,{w[i],w[i]} };
            dp2[i] = { 0,{w[i],w[i]} };
            visit[i] = true;
        }
    }
    dfs(0);
    vector<bool>visit1(n, false);
    ll ans = 0;
    bfs(0);
    for (int i = 0; i < n; i++) {
        if (!visit1[sed[i]]) {
            ans += dp1[sed[i]].first;
            int tmp12 = i;
            while (tmp12!=-1) {
                visit1[tmp12] = true;
                tmp12 = pre[tmp12];
            }
        }
    }
    cout << ans;
}*/
int main() {
    int n, k;
    cin >> n >> k;
    multiset<int>set1;
    vector<int>vec(n+k);
    ll sum = 0;
    for (int i = 0; i < n + k; i++) {
        cin >> vec[i];
        set1.insert(vec[i]);
        sum += vec[i];
    }
    for (int i = 0; i < n + k; i++) {
        ll sum1 = sum - vec[i];
        set1.erase(set1.find(vec[i]));
        auto it = set1.begin();
        int a1 = *it;
        ++it;
        int a2 = *it;
        int d = a2 - a1;
        ll sum2 = (2 * a1 + (n - 1) * d) * n / 2;
        if (sum2 == sum1) {
            for (int j = 0; j < n + k; j++) {
                if (j != i)
                    cout << vec[j] << " ";
            }
            break;
        }
        set1.insert(vec[i]);
    }
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13