oj.uz

Submission #1088914

# Submission time Handle Problem Language Result Execution time Memory
1088914 2024-09-15T14:02:01 Z raczek Tiles (BOI24_tiles) C++17
4 / 100
 2000 ms 54756 KB 
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	set<pair<int, int> > segs[2]; //.first = koniec, .second = poczatek
	vector<int> np(2);
	int result = 0;
	auto add = [&](int x, int y1, int y2)
	{
		x = x%2;
		auto it = segs[x].insert({y2, y1}).first;
		if(abs(y2 - y1)%2 == 1) np[x]++;
		if(it != segs[x].begin())
		{
			it--;
			if(it->first == y1)
			{
				if(abs(it->first - it->second)%2 == 1) np[x]--;
				if(abs(y2 - y1)%2 == 1) np[x]--;
				segs[x].erase(make_pair(it->first, it->second));
				segs[x].erase(make_pair(y2, y1));
				y1 = it->second;
				it = segs[x].insert(make_pair(y2, y1)).first;
				if(abs(y2 - y1)%2 == 1) np[x]++;
			}
			else
			it++;
		}
		it++;
		if(it != segs[x].end())
		{
			if(it->second == y2)
			{
				if(abs(it->first - it->second)%2 == 1) np[x]--;
				if(abs(y1 - y2)%2 == 1) np[x]--;
				segs[x].erase(make_pair(it->first, it->second));
				segs[x].erase(make_pair(y2, y1));
				y2 = it->first;
				segs[x].insert(make_pair(y2, y1));
				if(abs(y2 - y1)%2 == 1) np[x]++;
			}
		}
	};
	auto sub = [&](int x, int y1, int y2)
	{
		x = x%2; x^=1;
		auto it1 = segs[x].upper_bound(make_pair(y1, -1));
		if(it1 != segs[x].end() && it1->second <= y1) {cout<<result; exit(0);}
		auto it2 = segs[x].upper_bound(make_pair(y2, -1));
		if(it2 != segs[x].end() && it2->second <= y2) {cout<<result; exit(0);}
		if(it1 != it2) {cout<<result; exit(0);}
		x^=1;
		vector<pair<int, int> > toAdd;
		for(auto it = segs[x].upper_bound(make_pair(y1, -1)); it != segs[x].end() 
		&& it->second <= y2; ++it)
		{
			if(abs(it->first - it->second)%2 == 1) np[x]--;
			if(it->second < y1)
			{
				if(abs(it->second - y1)%2 == 1) np[x]++;
				toAdd.push_back(make_pair(y1, it->second));
			}
			if(it->first > y2)
			{
				if(abs(it->first - y2)%2 == 1) np[x]++;
				toAdd.push_back(make_pair(it->first, y2));
			}
		}
		for(auto v : toAdd) segs[x].insert(v);
	};
	int n, m;
	cin>>n>>m;
	vector<pair<int, int> > pts(n);
	for(auto& v : pts) {cin>>v.first>>v.second;}
	auto cmp = [&](pair<int, int> a, pair<int, int> b) {
		long long ax = a.first, ay = a.second, bx = b.first, by = b.second;
		return ax*by - ay*bx;
	};
	long long area = 0;
	for(int i=0;i<n;i++) area += cmp(pts[i], pts[(i+1)%n]);
	if(area < 0) reverse(pts.begin(), pts.end());
	debug(pts);
	vector<pair<pair<int, bool>, pair<int, int> > > events;
	for(int i=0;i<n;i++)
	{
		if(pts[i].first != pts[(i+1)%n].first) continue;
		pair<pair<int, bool>, pair<int, int> > toAdd;
		if(pts[i].second < pts[(i+1)%n].second)
		{toAdd.second = make_pair(pts[i].second, pts[(i+1)%n].second);}
		else toAdd.second = make_pair(pts[(i+1)%n].second, pts[i].second);
		if(pts[i].second < pts[(i+1)%n].second) toAdd.first.second = 0;
		if(pts[i].second > pts[(i+1)%n].second) toAdd.first.second = 1;
		toAdd.first.first = pts[i].first;
		events.push_back(toAdd);
	}
	sort(events.begin(), events.end());
	result = events[0].first.first;
	int prev = -1;
	for(auto& v : events)
	{
		debug(v);
		debug(segs[0]);
		debug(segs[1]);
		if(prev != v.first.first)
		{
			if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)^1].size() == 0) 
				{result = v.first.first;}
			else if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)].size() == 0) 
				result = v.first.first-1;	
		}
		if(v.first.second == 1) add(v.first.first, v.second.first, v.second.second);
		if(v.first.second == 0) sub(v.first.first, v.second.first, v.second.second);
	//	if(&v == &events[events.size()-1]) continue;
	//	if((*(&v + 1)).first.first != v.first.first)
	//		if(np[0] == 0 && np[1] == 0 && segs[(v.first.first+1)%2].size() == 0)
				prev = v.first.first;
	}
//	if(np[0] == 0 && np[1] == 0 && segs[0].size() == 0 && segs[1].size() == 0) result = m+1;
	cout<<result;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Incorrect 1 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 50 ms 10748 KB Output is correct
3 Correct 33 ms 8528 KB Output is correct
4 Correct 26 ms 5712 KB Output is correct
5 Correct 553 ms 5840 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 36 ms 7780 KB Output is correct
9 Correct 37 ms 7908 KB Output is correct
10 Execution timed out 2074 ms 54756 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 20896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Incorrect 1 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -