Submission #985479

#	Time	Username	Problem	Language	Result	Execution time	Memory
985479		Math4Life2020	Split the sequence (APIO14_sequence)	C++17	0 / 100	17 ms	3880 KiB

sequence

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

void solve(long long N, long long K, vector<long long> a, vector<long long> a0, long long K0) {
	if (K0>K) {
		long long tval = 0;
		for (long long i=0;i<N;i++) {
			tval += a[i];
		}
		tval = tval*tval;
		deque<long long> d[K+1];
		long long dsums[K+1];
		for (long long i=0;i<=K;i++) {
			dsums[i]=0;
		}
		for (long long i=0;i<N;i++) {
			d[0].push_back(a[i]);
			dsums[0] += a[i];
		}
		for (long long t=0;t<(2*N);t++) {
			for (long long i=0;i<K;i++) {
				while (1) {
					long long r = d[i].back();
					if (max(dsums[i]-r,dsums[i+1]+r)<max(dsums[i],dsums[i+1])) {
						d[i].pop_back();
						d[i+1].push_front(r);
						dsums[i]=dsums[i]-r;
						dsums[i+1]=dsums[i+1]+r;
					} else {
						break;
					}
				}
			}
		}
		for (long long i=0;i<=K;i++) {
			tval -= dsums[i]*dsums[i];
			/*cout << "i="<<i<<", dsums="<<dsums[i]<<"\n";
			for (long long x: d[i]) {
				cout << "term: "<<x<<"\n";
			}*/
		}
		tval = tval/2;
		cout << tval <<"\n";
		int del = K0-K;
		set<int> noninc;
		for (int i=0;i<(a0.size()-1);i++) {
			noninc.insert(i);
		}
		int llnz = -1;
		for (int i=0;i<a0.size();i++) {
			if (a0[i] != 0) {
				llnz = i;
			}
		}
		for (int i=0;i<a0.size();i++) {
			if ((a0[i] != 0)) {
				if (i != llnz) {
					noninc.erase(i);
				}
			}
		}
		for (int i=0;i<del;i++) {
			noninc.erase(noninc.begin());
		}
		string outstr;
		for (int i=0;i<(a0.size()-1);i++) {
			if (noninc.find(i)==noninc.end()) {
				outstr += to_string(i);
				outstr += " ";
			}
		}
		outstr = outstr.substr(0,(outstr.length()-1));
		cout << outstr;
	} else {
		long long tval = 0;
		for (long long i=0;i<N;i++) {
			tval += a[i];
		}
		tval = tval*tval;
		deque<long long> d[K+1];
		long long dsums[K+1];
		for (long long i=0;i<=K;i++) {
			dsums[i]=0;
		}
		for (long long i=0;i<N;i++) {
			d[0].push_back(a[i]);
			dsums[0] += a[i];
		}
		for (long long t=0;t<(2*N);t++) {
			for (long long i=0;i<K;i++) {
				while (1) {
					long long r = d[i].back();
					if (max(dsums[i]-r,dsums[i+1]+r)<max(dsums[i],dsums[i+1])) {
						d[i].pop_back();
						d[i+1].push_front(r);
						dsums[i]=dsums[i]-r;
						dsums[i+1]=dsums[i+1]+r;
					} else {
						break;
					}
				}
			}
		}
		for (long long i=0;i<=K;i++) {
			tval -= dsums[i]*dsums[i];
			/*cout << "i="<<i<<", dsums="<<dsums[i]<<"\n";
			for (long long x: d[i]) {
				cout << "term: "<<x<<"\n";
			}*/
		}
		tval = tval/2;
		cout << tval <<"\n";
		string ans;
		int rtot = 0;
		for (int q=0;q<K;q++) {
			int count = 0;
			while (count<(d[q].size())) {
				if (a0[rtot] != 0) {
					count++;
				}
				rtot++;
			}
			ans += to_string(rtot);
			if (q != (K-1)) {
				ans += " ";
			}
		}
		cout << ans;
	}
}

int main() {
	long long N,K; cin >> N >> K;
	vector<long long> a;
	vector<long long> a0;
	for (long long i=0;i<N;i++) {
		long long x; cin >> x;
		a0.push_back(x);
		if (x != 0) {
			a.push_back(x);
		}
	}
	int K0 = K;
	K = min(K,(long long) (a.size()-1));
	solve(a.size(),K,a,a0,K0);
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>, std::vector<long long int>, long long int)':
sequence.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i=0;i<(a0.size()-1);i++) {
      |                ~^~~~~~~~~~~~~~
sequence.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i=0;i<a0.size();i++) {
      |                ~^~~~~~~~~~
sequence.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (int i=0;i<a0.size();i++) {
      |                ~^~~~~~~~~~
sequence.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i=0;i<(a0.size()-1);i++) {
      |                ~^~~~~~~~~~~~~~
sequence.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    while (count<(d[q].size())) {
      |           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29