Submission 123701 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
123701	30/04/2018 9:01:51	jc	F - Array	Accepted	593	18.5 MiB	GNU G++11 5.1.0

Code

#include <bits/stdc++.h>
#include <ext/algorithm>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define endl '\n'

typedef long long ll;

const ll oo = 0x3f3f3f3f3f3f3f3f;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

int n, k;
	cin >> n >> k;

set<pair<int, ll>> A;
	set<pair<ll, int>> B;

A.insert({0, oo}); A.insert({n + 1, oo});
	B.insert({oo, 0}); B.insert({oo, n + 1});

vector<int> val(n);

for (int i = 1; i <= n; ++i)
	{
		cin >> val[i - 1];

A.insert({i, val[i - 1]});
		B.insert({val[i - 1], i});
	}

ll ans = 0;
	stack<tuple<int, int, int>> stk;

for (int i = 0; i < k; ++i)
	{
		pair<ll, int> beg = *B.begin();
		ans += beg.first;

pair<int, ll> a = *prev(A.find({beg.second, beg.first}));
		pair<int, ll> b = *next(A.find({beg.second, beg.first}));

A.erase({beg.second, beg.first});
		A.erase(a);
		A.erase(b);

B.erase(beg);
		B.erase({a.second, a.first});
		B.erase({b.second, b.first});

B.insert({a.second + b.second - beg.first, beg.second});
		A.insert({beg.second, a.second + b.second - beg.first});

stk.push(make_tuple(a.first, beg.second, b.first));
	}

set<int> final;
	for (auto &p : A)
		final.insert(p.first);

for (; !stk.empty(); stk.pop())
	{
		int a, b, c;
		tie(a, b, c) = stk.top();

if (final.count(b))
		{
			final.erase(b);
			final.insert(a);
			final.insert(c);
		}
		else
		{
			final.insert(b);
			final.erase(a);
			final.erase(c);
		}
	}

vector<int> res;
	for (int i = 1; i <= n; ++i)
		if (!final.count(i))
			res.push_back(i);

cout << ans << endl;

for (int i = 1; i <= k; ++i)
		cout << res[i - 1] << " \n"[i == k];
	
	return 0;
}

Judgement Details

Case#1 [425984 bytes][47 ms]: ok contestant found the optimal answer: 1000000000
Case#2 [425984 bytes][16 ms]: ok contestant found the optimal answer: 340
Case#3 [14573568 bytes][593 ms]: ok contestant found the optimal answer: 411321413
Case#4 [17899520 bytes][437 ms]: ok contestant found the optimal answer: 100755932
Case#5 [430080 bytes][32 ms]: ok contestant found the optimal answer: 537092323
Case#6 [1925120 bytes][47 ms]: ok contestant found the optimal answer: 492516409
Case#7 [430080 bytes][15 ms]: ok contestant found the optimal answer: 44
Case#8 [425984 bytes][12 ms]: ok contestant found the optimal answer: 773
Case#9 [724992 bytes][15 ms]: ok contestant found the optimal answer: 493503
Case#10 [2314240 bytes][47 ms]: ok contestant found the optimal answer: 101056127
Case#11 [7569408 bytes][124 ms]: ok contestant found the optimal answer: 129968
Case#12 [14569472 bytes][531 ms]: ok contestant found the optimal answer: 375524431
Case#13 [19386368 bytes][249 ms]: ok contestant found the optimal answer: 75975
Case#14 [425984 bytes][47 ms]: ok contestant found the optimal answer: 2664
Case#15 [458752 bytes][15 ms]: ok contestant found the optimal answer: 140256
Case#16 [4362240 bytes][62 ms]: ok contestant found the optimal answer: 803105
Case#17 [14852096 bytes][578 ms]: ok contestant found the optimal answer: 162316123
Case#18 [458752 bytes][47 ms]: ok contestant found the optimal answer: 1002499
Case#19 [688128 bytes][15 ms]: ok contestant found the optimal answer: 1249999
Case#20 [14766080 bytes][398 ms]: ok contestant found the optimal answer: 250954854

Matcom Online Grader