Submission #67115

#	Time	Username	Problem	Language	Result	Execution time	Memory
67115		cdemirer	DEL13 (info1cup18_del13)	C++17	0 / 100	20 ms	756 KiB

del13

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vi> vvi;
typedef pair<double, double> dodo;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int N, M;
bool arr[100000];
void next_zero(int &p) {
	while (p < N && arr[p]) p++;
}
void next_one(int &p) {
	while (p < N && !arr[p]) p++;
}

vi instructions;

bool process(ii interval) {
	vi group_sz(1), group_bgn(1);
	int ptr = interval.first;
	group_bgn[0] = ptr;
	bool type = false;
	while (ptr <= interval.second) {
		if (arr[ptr] == type) {
			group_sz[group_sz.size()-1]++;
		} else {
			type = arr[ptr];
			group_sz.pb(1);
			group_bgn.pb(ptr);
		}
		ptr++;
	}
	/*for (int i = 0; i < group_sz.size(); i++) {
		cerr << "g" << i << "  sz: " << group_sz[i] << "  bgn: " << group_bgn[i] << endl;
	}*/
	bool flag = true;
	vi tmp;
	for (int i = 0; i < group_sz.size(); i += 2) tmp.pb(group_sz[i]);
	vi mn(tmp.size()), mx(tmp.size());
	for (int i = 0; i < tmp.size(); i++) mn[i] = mx[i] = tmp[i];
	for (int i = 0; i < tmp.size()-1; i++) {
		if (tmp[i] >= 4 && tmp[i] % 2 == 0) mn[i] -= (tmp[i] - 2);
		if (tmp[i] >= 3 && tmp[i] % 2 == 1) mn[i] -= (tmp[i] - 1);
		if (mn[i] > 0) {
			if (mn[i] <= mx[i+1]) {
				int t = mn[i];
				mn[i] -= mx[i+1];
				mx[i+1] -= t;
				mn[i+1] -= mx[i];
			} else {
				cerr << "Breaked at " << i << " (min_val="<<mn[i] - mx[i+1]<<" above 0)" << endl;
				flag = false;
				break;
			}
		}
		else if (mx[i] >= 0) {
			mn[i+1] -= mx[i];
			if (mn[i+1] < 0 && mn[i+1] % 2 == -1 && mn[i+1] + mx[i] > 0) {
				mn[i+1] += mx[i];
				/*flag = false;
				cerr << "the complex condition" << endl;
				break;*/
			}
		}
		else {
			flag = false;
			cerr << "Breaked at " << i << " (max_val below 0)" << endl;
			break;
		}
	}
	if (tmp[tmp.size()-1] >= 4 && tmp[tmp.size()-1] % 2 == 0) mn[tmp.size()-1] -= (tmp[tmp.size()-1] - 2);
	if (tmp[tmp.size()-1] >= 3 && tmp[tmp.size()-1] % 2 == 1) mn[tmp.size()-1] -= (tmp[tmp.size()-1] - 1);
	if (mn[tmp.size()-1] > 0) flag = false;
	if (mx[tmp.size()-1] < 0) flag = false;
	/*cerr << "tmprange: ";
	for (int i = 0; i < tmp.size(); i++) cerr << tmp[i] << " ";
	cerr << endl;
	cerr << "maxrange: ";
	for (int i = 0; i < tmp.size(); i++) cerr << mx[i] << " ";
	cerr << endl;
	cerr << "minrange: ";
	for (int i = 0; i < tmp.size(); i++) cerr << mn[i] << " ";
	cerr << endl;*/
	return flag;
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int TC; cin >> TC;
	while (TC--) {
		cin >> N >> M;
		memset(arr, 0, sizeof(arr));
		for (int i = 0; i < M; i++) {
			int x; cin >> x; x--; arr[x] = true;
		}
		int ptr = 0;
		vii intervals;
		while (true) {
			ii interval;
			next_zero(ptr);
			if (ptr == N) break;
			interval.first = ptr;
			while (true) {
				next_one(ptr);
				if (ptr >= N-1 || arr[ptr+1]) {
					interval.second = ptr-1;
					break;
				}
				ptr++;
			}
			intervals.pb(interval);
			if (ptr == N) break;
		}
		/*for (int i = 0; i < intervals.size(); i++) {
			cerr << "interval " << i << ": " << intervals[i].first << "-" << intervals[i].second << endl;
		}*/
		instructions.clear();
		bool flag = true;
		for (int i = 0; i < intervals.size(); i++) {
			flag &= process(intervals[i]);
			if (!flag) break;
		}
		if (flag) {
			cout << instructions.size() << '\n';
			for (int i = 0; i < instructions.size(); i++) {
				cout << instructions[i] << " ";
			}
			cout << '\n';
		} else {
			cout << -1 << '\n';
		}
	}
	
	return 0;
}

Compilation message (stderr)

del13.cpp: In function 'bool process(ii)':
del13.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < group_sz.size(); i += 2) tmp.pb(group_sz[i]);
                  ~~^~~~~~~~~~~~~~~~~
del13.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tmp.size(); i++) mn[i] = mx[i] = tmp[i];
                  ~~^~~~~~~~~~~~
del13.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tmp.size()-1; i++) {
                  ~~^~~~~~~~~~~~~~
del13.cpp: In function 'int main(int, char**)':
del13.cpp:127:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < intervals.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~
del13.cpp:133:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < instructions.size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30