QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554932#7517. Flying Ship StoryOIer_kzcWA 233ms3952kbC++142.8kb2024-09-09 18:09:582024-09-09 18:09:59

Judging History

你现在查看的是最新测评结果

  • [2024-09-09 18:09:59]
  • 评测
  • 测评结果:WA
  • 用时:233ms
  • 内存:3952kb
  • [2024-09-09 18:09:58]
  • 提交

answer

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)
#define eb emplace_back

using namespace std;

typedef unsigned long long ULL;
constexpr int N = 200005, TC = 4 * N, MC = N * 60;

struct Vset {
	int t, x, y, z, w;
	bool contain(int sx, int sy) const {
		if (t == 5) {
			return false;
		}
		if (t == 5 && z == sx && y == sy) {
			return true;
		}
		if ((t == 4 || t == 5) && x == sx && y == sy) {
			return true;
		}
		if (t == 1 && y == sy || t == 2 && x == sx || t == 0 && (x == sx || y == sy)) {
			return true;
		}
		return false;
	}
	bool contain(const Vset &s) const {
		if (s.t == 5) {
			return true;
		}
		if (s.t == 4) {
			return contain(s.x, s.y);
		}
		if (s.t == 3) {
			return contain(s.x, s.y) && contain(s.z, s.w);
		}
		if (t > 2) {
			return false;
		}
		if (s.t == 2) {
			return t != 1 && x == s.x;
		}
		if (s.t == 1) {
			return t != 2 && y == s.y;
		}
		return t == 0 && x == s.x && y == s.y;
	}
};

constexpr Vset emt = (Vset){5};

Vset operator & (const Vset &a, const Vset &b) {
	if (a.t > b.t) {
		return (b & a);
	}
	if (a.contain(b)) {
		return b;
	}
	if (b.t > 3) {
		return emt;
	}
	if (b.t == 3) {
		if (a.contain(b.x, b.y)) {
			return (Vset){4, b.x, b.y};
		}
		if (a.contain(b.z, b.w)) {
			return (Vset){4, b.z, b.w};
		}
		return emt;
	}
	if (b.t == 2) {
		return a.t == 2 ? emt : (Vset){4, a.y, b.x};
	}
	if (b.t == 1) {
		return a.t == 1 ? emt : (Vset){4, a.x, b.y};
	}
	if (a.t || b.t) {
		LOG("ERR\n");
		while (true);
	}
	if (a.y == b.y) {
		return (Vset){1, 0, a.y};
	}
	if (a.x == b.x) {
		return (Vset){2, a.x, 0};
	}
	return (Vset){3, a.x, b.y, a.y, b.x};
}

struct Dat {
	int x, y, c;
	bool operator < (const Dat &t) const {
		return c > t.c;
	}
};
vector<Dat> v;

void ex(int x, int y, int c) {
	const Dat &t = {x, y, c};
	v.insert(lower_bound(v.begin(), v.end(), t), t);
	Vset andS = (Vset){0, v[0].x, v[0].y};
	for (int i = 1; i < v.size(); ++i) {
		bool ers = (andS.t == 5);
		int cx = 0, cy = 0;
		for (int j = 0; j < i; ++j) {
			if (v[i].x == v[j].x && v[i].y == v[j].y) {
				ers = true;
			}
			if (v[i].x == v[j].x) {
				++cx;
			}
			if (v[i].y == v[j].y) {
				++cy;
			}
		}
		ers |= (cx >= 2 || cy >= 2);
		if (ers) {
			v.erase(v.begin() + i);
		} else {
			andS = andS & (Vset){0, v[i].x, v[i].y};
		}
	}
}

int qry(int tx, int ty) {
	for (auto [x, y, c] : v) {
		if (x != tx && y != ty) {
			return c;
		}
	}
	return 0;
}

int main() {
	int q;
	scanf("%d", &q);
	int t, x, y, c, last = 0;
	while (q--) {
		scanf("%d%d%d", &t, &x, &y);
		x ^= last, y ^= last;
		if (t == 1) {
			scanf("%d", &c);
			c ^= last;
			ex(x, y, c);
		} else {
			printf("%d\n", last = qry(x, y));
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3952kb

input:

5
1 2 3 1
1 4 5 2
2 2 2
2 3 7
2 3 4

output:

2
1
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 208ms
memory: 3904kb

input:

1000000
2 370943499 431961772
1 1 1 11995570
2 37566858 838793045
1 11995571 11995569 908148975
2 11995571 11995571
1 1 3 716821068
2 67877937 3
1 11995571 11995571 771898489
2 38381714 99749723
1 915818844 915818847 729541681
2 592361351 915818846
1 783627722 783627722 639375021
2 102203700 8636489...

output:

0
11995570
0
11995570
915818845
783627723
915818845
0
0
915818845
0
783627723
0
904468304
904468304
904468304
915818845
904468304
915818845
904468304
915818845
0
904468304
0
915818845
915818845
0
0
915818845
915818845
0
921710773
0
921710773
998138906
921710773
0
921710773
998138906
0
998138906
0
99...

result:

ok 500000 lines

Test #3:

score: -100
Wrong Answer
time: 233ms
memory: 3916kb

input:

1000000
2 648544745 437316088
1 1 1 221075686
2 802693951 691188141
1 221075687 221075684 1036811136
2 771835961 178451319
1 820061031 820061031 560017372
2 829408420 820061028
1 293604539 293604539 699366423
2 293604539 293604539
1 1 2 610044241
2 50747012 885321059
1 942633132 942633132 603537610
...

output:

0
221075686
820061030
293604538
0
942633133
942633133
27478144
820061030
820061030
900696946
27478144
942633133
942633133
0
772167494
27478144
891145650
900696946
772167494
891145650
918281274
772167494
772167494
772167494
772167494
772167494
942633133
918281274
891145650
918281274
891145650
8911456...

result:

wrong answer 1609th lines differ - expected: '994844445', found: '0'