QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116781#5155. Faster Than Lightbatrr#RE 2ms5568kbC++234.8kb2023-06-30 04:17:042023-06-30 04:17:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 04:17:05]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:5568kb
  • [2023-06-30 04:17:04]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}
int n;
const int maxN = 2e5 + 10;
int x[maxN][2];
int y[maxN][2];
bool cmp(tuple<ll,ll,int>& a, tuple<ll,ll,int>& b) {
    ll X1 = get<0>(a);
    ll Y1 = get<1>(a);
    ll X2 = get<0>(b);
    ll Y2 = get<1>(b);
    assert(X1 > 0 && Y1 > 0 && X2 > 0 && Y2 > 0);
    return (X1 * Y2 < X2 * Y1);
}
bool check() {
    vector<int> lower(n), upper(n);
    iota(lower.begin(), lower.end(), 1);
    iota(upper.begin(), upper.end(), 1);
    sort(lower.begin(), lower.end(), [&](int i, int j) {
        return make_pair(x[i][0], y[i][0]) < make_pair(x[j][0], y[j][0]);
    });

    sort(upper.begin(), upper.end(), [&](int i, int j) {
        return make_pair(x[i][1], y[i][1]) < make_pair(x[j][1], y[j][1]);
    });

    vector<pair<ll,ll>> pt_l, pt_u;
    for (int id : lower) {
        ll X = x[id][0];
        ll Y = y[id][0];
        while (!pt_l.empty() && pt_l.back().second <= Y) {
            pt_l.pop_back();
        }
        while (pt_l.size() >= 2) {
            auto t1 = pt_l[pt_l.size() - 2];
            auto t2 = pt_l.back();
            if ((t2.second - Y) * (t2.first - t1.first) >= (X - t2.first) * (t1.second - t2.second)) {
                break;
            }
            else {
                pt_l.pop_back();
            }
        }
        pt_l.emplace_back(X, Y);
    }

    for (int id : upper) {
        ll X = x[id][1];
        ll Y = y[id][1];
        if (!pt_u.empty() && pt_u.back().second <= Y) {
            continue;
        }
        while (pt_u.size() >= 2) {
            auto t1 = pt_u[pt_u.size() - 2];
            auto t2 = pt_u.back();
            if ((t2.second - Y) * (t2.first - t1.first) <= (X - t2.first) * (t1.second - t2.second)) {
                break;
            }
            else {
                pt_u.pop_back();
            }
        }
        pt_u.emplace_back(X, Y);
    }

    const ll INF = (ll)1e9 + 228;
    vector<tuple<ll, ll, int>> events;
    for (int i = 0; i + 1 < pt_l.size(); i++) {
        events.emplace_back(pt_l[i].second - pt_l[i + 1].second, pt_l[i + 1].first - pt_l[i].first, i);
    }
    for (int i = 0; i + 1 < events.size(); i++) {
        assert(cmp(events[i], events[i + 1]));
    }
    for (int i = (int)pt_u.size() - 2; i >= 0; i--) {
        events.emplace_back(pt_u[i].second - pt_u[i + 1].second, pt_u[i + 1].first - pt_u[i].first, ~i);
    }
    sort(events.begin(), events.end(), cmp);
    int ID_U = pt_u.size() - 1;
    int ID_L = 0;
    ll PRV_A = 0;
    ll PRV_B = 1;
    for (auto& it : events) {
        ll A = get<0>(it);
        ll B = get<1>(it);
        if (PRV_A * pt_l[ID_L].first + PRV_B * pt_l[ID_L].second <= PRV_A * pt_u[ID_U].first + PRV_B * pt_u[ID_U].second) {
            return true;
        }
        if (A * pt_l[ID_L].first + B * pt_l[ID_L].second <= A * pt_u[ID_U].first + B * pt_u[ID_U].second) {
            return true;
        }
        if (get<2>(it) >= 0) {
            ID_L++;
        }
        else {
            ID_U--;
        }
        PRV_A = A;
        PRV_B = B;
    }
    assert(ID_L == pt_l.size() - 1);
    assert(ID_U == 0);
    PRV_A = 1;
    PRV_B = 0;
    if (PRV_A * pt_l[ID_L].first + PRV_B * pt_l[ID_L].second <= PRV_A * pt_u[ID_U].first + PRV_B * pt_u[ID_U].second) {
        return true;
    }
    return false;


}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> x[i][j] >> y[i][j];
        }
    }
    for (int iter = 0; iter < 2; iter++) {
        if (check()) {
            cout << "possible\n";
            return ;
        }

        for (int i = 1; i <= n; i++) {
            swap(y[i][0], y[i][1]);
            y[i][0] *= -1;
            y[i][1] *= -1;
        }
    }
    cout << "impossible\n";
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5568kb

input:

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

4
1 1 2 2
1 3 2 4
3 1 4 2
3 3 4 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5536kb

input:

4
0 1 1 1000000000
1 0 999999999 1
999999999 0 1000000000 999999999
2 999999999 999999999 1000000000

output:

possible

result:

ok single line: 'possible'

Test #6:

score: 0
Accepted
time: 2ms
memory: 5468kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 999999999 1000000000

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 1000000000 1000000000

output:

possible

result:

ok single line: 'possible'

Test #8:

score: -100
Dangerous Syscalls

input:

199999
433914929 216935871 433914930 216935872
621822279 310889546 621822280 310889547
395914333 197935573 395914334 197935574
582775641 291366227 582775642 291366228
658726133 329341473 658726134 329341474
71689261 35823037 71689262 35823038
453260967 226608890 453260968 226608891
249802825 1248798...

output:


result: