QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#610029#9427. Collect the Coinspropane#WA 37ms3704kbC++202.5kb2024-10-04 14:45:002024-10-04 14:45:03

Judging History

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

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-04 14:45:03]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:3704kb
  • [2024-10-04 14:45:00]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<pair<int, int> > p(n);
        bool ok = true;
        for(int i = 0; i < n; i++){
            cin >> p[i].first >> p[i].second;
            if (i - 2 >= 0 and p[i].first == p[i - 2].first){
                ok = false;
            }
        }
        if (!ok){
            cout << -1 << '\n';
            continue;
        }

        auto check = [&](int mid){

            vector<pair<LL, LL> > q(n);
            for(int i = 0; i < n; i++){
                auto [t, x] = p[i];
                q[i] = {1LL * mid * t + x, 1LL * mid * t - x};
            }

            auto f = [&](int a, int b){
                return q[a].first <= q[b].first and q[a].second <= q[b].second;
            };

            set<pair<LL, LL> > s;

            auto insert = [&](pair<LL, LL> p){
                auto it = s.upper_bound(p);
                if (it != s.begin() and prev(s.begin())->second <= p.second) return;
                while(it != s.end() and it->second >= p.second){
                    it = s.erase(it);
                }
                s.insert(p);
            };

            bool ok = true;
            for(int i = 1; i < q.size(); i++){
                if (!ok and s.empty()) return false;
                bool add = false, flag = true;
                if (ok) add = true;
                if (!f(i - 1, i)){
                    ok = false;
                    flag = false;
                }
                if (!add){
                    auto it = s.upper_bound(q[i]);
                    if (it != s.begin()){
                        --it;
                        if (it->second <= q[i].second){
                            add = true;
                        }
                    }
                }
                if (!flag) s.clear();
                if (add){
                    insert(q[i - 1]);
                }
            }
            return true;
        };

        int l = 0, r = 1e9;
        while(l < r){
            int mid = (l + r) / 2;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << r << '\n';
    }

}

詳細信息

Test #1:

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

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 37ms
memory: 3704kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

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

result:

wrong answer 10th lines differ - expected: '2', found: '1'