QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#554936 | #7517. Flying Ship Story | OIer_kzc | WA | 235ms | 3876kb | C++14 | 2.8kb | 2024-09-09 18:11:40 | 2024-09-09 18:11:40 |
Judging History
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;
struct Vset {
int t, x, y, z, w;
bool contain(int sx, int sy) const {
if (t == 5) {
return false;
}
if (t == 4) {
return x == sx && y == sy;
}
if (t == 3) {
return x == sx && y == sy || z == sx && w == sy;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 214ms
memory: 3876kb
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: 235ms
memory: 3800kb
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'