Problem Info
Stuck in a Rut
Question
Hello, when I run the sample code on my local computer I get the correct answer, but when I submitted it to the server it said runtime error or memory exceeded on sample.
What I’ve Tried
I do not believe there is any undefined behavior because I have run the code several times even after restarting my computer and have gotten the same correct answer instantly. I have also looked at how the solution gets its data, and my input is the same. After I run the code, the answer is always correct and comes back instantly. In addition, my solution should be at most quadratic or cubic time complexity. I have tried submitting the code several times, making sure to select the right language or file. However, when I submit it, it spins for a couple of seconds and then gives me the error.
My Work
#include <bits/stdc++.h>
#define NO_INTSEC 9999999
using namespace std;
struct intsec {
int t; // time
int x; // x pos
int y; // y pos
int curr; // cow walking in
int past; // cow walked past
};
int main() {
int n;
cin >> n;
string direction[n];
int x[n];
int y[n];
vector<intsec> intsecs; // crash time and cow #
vector<int> cellsEaten;
cellsEaten.resize(n);
fill(cellsEaten.begin(), cellsEaten.end(), -1); // assume inf
for (int i = 0; i < n; ++i)
cin >> direction[i] >> x[i] >> y[i];
// get all possible crashes
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) // skip same cow
continue;
if (direction[i] == "N" && direction[j] == "N") { // this and other north
if (y[i] < y[j] && x[i] == x[j]) {
intsecs.push_back({
y[j] - y[i], // time
x[i], y[j], // x and y pos
i, j // current and previous cow
});
}
continue;
}
if (direction[i] == "E" && direction[j] == "E") { // this and other east
if (x[i] < x[j] && y[i] == y[j]) {
intsecs.push_back({
x[j] - x[i], // time
x[j], y[i], // x and y pos
i, j // current and previous cow
});
}
continue;
}
int thisTime, otherTime, xPos, yPos;
if (direction[i] == "N" && direction[j] == "E") { // this north other east
otherTime = x[i] - x[j];
thisTime = y[j] - y[i];
xPos = x[i];
yPos = y[j];
}
if (direction[i] == "E" && direction[j] == "N") { // this east other north
thisTime = x[j] - x[i];
otherTime = y[i] - y[j];
xPos = x[j];
yPos = y[i];
}
if (thisTime > 0 && otherTime > 0 && thisTime > otherTime) {
intsecs.push_back({
thisTime, // time
xPos, yPos, // x and y pos
i, j // current and previous cow
});
}
}
}
// prune crashes
while (1) {
// get min time
intsec min = {NO_INTSEC, 0, 0, 0, 0};
for (int i = 0; i < intsecs.size(); ++i) {
if (intsecs[i].t < min.t)
min = intsecs[i];
}
// set cells eaten
if (min.t == NO_INTSEC)
break;
cellsEaten[min.curr] = min.t;
// remove cow from intersections
intsecs.erase(intsecs.begin() + min.curr);
// remove invalid intersections of cow
for (int i = 0; i < intsecs.size(); ++i) {
intsec intsec = intsecs[i];
if (intsec.past == min.curr) {
if (direction[min.curr] == "N" && intsec.y > min.y) { // intersected with north one
intsecs.erase(intsecs.begin() + i);
}
if (direction[min.curr] == "E" && intsec.x > min.x) { // intersected with east one
intsecs.erase(intsecs.begin() + i);
}
}
}
}
for (int cells : cellsEaten) {
if (cells == -1) cout << "Infinity\n";
else cout << cells << "\n";
}
}