oj.uz

Submission #45194

# Submission time Handle Problem Language Result Execution time Memory
45194 2018-04-11T19:00:12 Z Bruteforceman DEL13 (info1cup18_del13) C++11
100 / 100
 123 ms 8252 KB 
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
vector <int> v;
vector <int> pile;
vector <int> opt;

set <int> s;
int keep[200010];

void two(int i) {
	auto p = s.lower_bound(v[i]);
	auto q = (--p);
	auto r = (--p);
	auto y = (--p);
	opt.push_back(*r);
	s.erase(q);
	s.erase(y);
	pile[i] -= 2;
}
void one(int x) {
	auto p = s.lower_bound(v[x]);	
	opt.push_back(*p);
	auto q = (--p);
	++p;
	auto r = (++p);
	s.erase(q);
	s.erase(r);
	pile[x] -= 1;
	pile[x + 1] -= 1;
}

void make_two(int x) {
	int cur = pile[x];
	while(cur > 2) {
		two(x);
		cur -= 2;
	}
}

bool check(int l, int r, vector <int> &v) {
	if(l > r) return true;
	if((r - l + 1) % 2 == 0) {
		for(int i = l; i <= r; i++) {
			make_two(i);
		}
		for(int i = l; i <= r; i += 2) {
			one(i);
			one(i);
		}
		return true;
	}
	int idx = -1;
	for(int i = l+1; i <= r; i += 2) {
		if(v[i] > 2) {
			idx = i;
			break;
		}
	}
	if(idx != -1) {
		make_two(idx - 1);
		one(idx - 1);
		one(idx - 1);
		
		for(int i = l; i <= r; i++) {
			if(i != idx-1) make_two(i);
		}	
		for(int i = l; i < idx - 1; i += 2) {
			one(i);
			one(i);
		}
		for(int i = idx; i <= r; i += 2) {
			one(i);
			one(i);
		}
		return true;
	}
	return false;
}

void doit(int l, int r) {
	if(keep[l] == 0) {
		while(pile[l] > 1) {
			two(l);
		}
	}
	if(keep[r] == 0) {
		while(pile[r] > 1) {
			two(r);
		}
	}
	for(int i = l + 1; i < r; i++) {
		make_two(i);
	}
	for(int i = l; i < r; i += 1) {
		one(i);
	}
}

bool solve(int n) {
	if((n & 1) != (v.size() & 1)) return false;
	if(v.empty()) return false;
	s.clear();
	opt.clear();
	memset(keep, 0, sizeof keep);

	for(int i = 1; i <= n; i++) {
		s.insert(i);
	}

	v.insert(v.begin(), 0);
	v.push_back(n+1);

	pile.clear();
	pile.push_back(0);
	for(size_t i = 1; i < v.size(); i++) {
		pile.push_back(v[i] - v[i-1] - 1);
	}
	pile.push_back(0);

	vector <pii> range;
	int prev = -1;
	for(size_t i = 0; i < pile.size(); i++) {
		if(pile[i] == 0) {
			if(prev != -1) {
				range.push_back(pii(prev, i-1));
			} 
			prev = -1;
		} else {
			if(prev == -1) {
				prev = i;
			}
		}
	}
	for(auto r : range) {
		vector <int> odd;
		for(int i = r.first; i <= r.second; i++) {
			if(pile[i] & 1) odd.push_back(i);
		}
		if(odd.empty()) {
			if(!check(r.first, r.second, pile)) return false;
			continue;
		}
		if(odd.size() & 1) return false;
		for(size_t i = 1; i+1 < odd.size(); i += 2) {
			if(pile[odd[i]] == 1 && pile[odd[i + 1]] == 1) {
				if(!check(odd[i] + 1, odd[i + 1] - 1, pile)) return false;
			} else {
				int sz = odd[i + 1] - odd[i] - 1;
				if(sz & 1) {
					if(pile[odd[i]] > 1) keep[odd[i]] = 1;
					else keep[odd[i + 1]] = 1;
				}
			}
		}
		if(pile[odd.front()] == 1) {
			if(!check(r.first, odd.front() - 1, pile)) return false;
		} else {
			int sz = odd.front() - r.first;
			if(sz & 1) {
				keep[odd.front()] = 1;
			}
		}
		if(pile[odd.back()] == 1) {
			if(!check(odd.back() + 1, r.second, pile)) return false;
		} else {
			int sz = r.second - odd.back();
			if(sz & 1) {
				keep[odd.back()] = 1;
			}
		}
		for(size_t i = 0; i+1 < odd.size(); i += 2) {
			doit(odd[i], odd[i + 1]);
		}
	}	
	range.clear();
	prev = -1;
	for(size_t i = 0; i < pile.size(); i++) {
		if(pile[i] == 0) {
			if(prev != -1) {
				range.push_back(pii(prev, i-1));
			} 
			prev = -1;
		} else {
			if(prev == -1) {
				prev = i;
			}
		}
	}
	for(auto i : range) {
		check(i.first, i.second, pile);
	}
	return true;
}

int main(int argc, char const *argv[])
{
	int t;
	scanf("%d", &t);
	while(t--) {
		int n, k;
		scanf("%d %d", &n, &k);
		v.clear();
		for(int i = 0; i < k; i++) {
			int x;
			scanf("%d", &x);
			v.push_back(x);
		}
		bool ans = solve(n);
		if(ans) {
			printf("%d\n", opt.size());
			for(auto i : opt) {
				printf("%d ", i);
			}
			printf("\n");
		} else {
			printf("-1\n");
		}
	}
	return 0;
}


/*

	int odd = -1;
	for(size_t i = 0; i < pile.size(); i++) {
		if(pile[i] & 1) {
			if(odd == -1) odd = i;
			else {
				for(int j = odd; j < i; j++) {
					pile[j]--;
					pile[j + 1]--;
				}
				odd = -1;
			}
		}
	}
	for(auto i : pile) {
		if(i < 0) return false; 
		cout << i << " ";
	}
	cout << endl;
*/

Compilation message

del13.cpp: In function 'int main(int, const char**)':
del13.cpp:211:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d\n", opt.size());
                   ~~~~~~~~~~^
del13.cpp:199:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
del13.cpp:202:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~~
del13.cpp:206:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1144 KB Output is correct
2 Correct 16 ms 1268 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1144 KB Output is correct
2 Correct 16 ms 1268 KB Output is correct
3 Correct 115 ms 1344 KB Output is correct
4 Correct 107 ms 1344 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1792 KB Output is correct
2 Correct 8 ms 1792 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1144 KB Output is correct
2 Correct 16 ms 1268 KB Output is correct
3 Correct 115 ms 1344 KB Output is correct
4 Correct 107 ms 1344 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 6 ms 1792 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1144 KB Output is correct
2 Correct 16 ms 1268 KB Output is correct
3 Correct 115 ms 1344 KB Output is correct
4 Correct 107 ms 1344 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 6 ms 1792 KB Output is correct
8 Correct 31 ms 2476 KB Output is correct
9 Correct 34 ms 3472 KB Output is correct
10 Correct 46 ms 4788 KB Output is correct
11 Correct 123 ms 8252 KB Output is correct