QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608097 | #9427. Collect the Coins | 2497201210 | TL | 905ms | 167320kb | C++20 | 1.6kb | 2024-10-03 18:28:42 | 2024-10-03 18:28:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e6+10;
const int P=1e9+7;
map<int,vector<int>>hh;
pair<int,vector<int>>md[N];
int idx=0;
bool check(int x) {
int l=-1e10;int r=1e10;
int d;
if(md[1].second.size()==1){
d=md[1].second[0];
}
else {
d=md[1].second[0];
l=r=md[1].second[1];
}
for(int i=2;i<=idx;i++){
int cha=md[i].first-md[i-1].first;
cha=cha*x;
l-=cha;r+=cha;
if(md[i].second.size()==2){
int pos1=md[i].second[0];int pos2=md[i].second[1];
if(pos1>=d-cha&&pos1<=d+cha&&pos2>=l&&pos2<=r){
d=pos1;
l=r=pos2;
}
else if(pos2>=d-cha&&pos2<=d+cha&&pos1>=l&&pos1<=r){
d=pos1;
l=r=pos2;
}
else{
return 0;
}
}
else{
int pos=md[i].second[0];
if(pos>=l&&pos<=r&&pos>=d-cha&&pos<=d+cha){
l=min(l,d-cha);
r=max(r,d+cha);d=pos;
}
else{
if(pos>=l&&pos<=r){
l=d-cha;
r=d+cha;
d=pos;
}
else if(pos>=d-cha&&pos<=d+cha){
d=pos;
}
else{
return 0;
}
}
}
}
return 1;
}
inline void solve() {
hh.clear();
int n;
cin>>n;
bool f=1;
for(int i=1; i<=n; i++) {
int a,b;
cin>>a>>b;
hh[a].push_back(b);
if(hh[a].size()>2)f=0;
}
if(f) {
idx=0;
for(auto&it:hh) {
md[++idx]= {it.first,it.second};
}
int l=0;
int r=1e9+100;
while(l<r) {
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
} else {
cout<<-1<<endl;
}
}
signed main() {
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 0
Accepted
time: 53ms
memory: 5240kb
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 2 2 0 2 5 0 1 5 1 2 0 0 0 1 4 2 0 2 1 3 0 3 2 3 2 5 3 1 1 0 1 1 1 0 2 0 1 0 1 0 2 1 0 2 3 4 4 1 1 1 0 1 3 0 1 4 4 3 0 0 2 2 6 4 2 1 0 0 1 0 2 1 2 0 1 1 3 0 0 1 2 0 3 0 2 2 2 1 0 0 0 5 1 2 0 6 1 1 1 2 2 2 0 3 1 4 3 6 0 8 1 1 3 0 2 2 4 1 1 0 0 0 7 2 2 1 0 0 3 1 2 1 1 2 5 3 0 3 3 3 5 ...
result:
ok 1135 lines
Test #3:
score: 0
Accepted
time: 819ms
memory: 122432kb
input:
1 1000000 2 57841 2 357142 3 496329 3 545446 4 503408 4 590762 5 78281 6 196926 6 349414 7 200245 8 953412 11 616898 12 592065 13 945945 15 20908 15 852722 16 221184 16 401521 17 884478 18 186072 18 931445 19 833560 20 314177 21 138453 21 731965 22 172104 23 595921 25 372617 27 545759 28 977029 30 4...
output:
994024
result:
ok single line: '994024'
Test #4:
score: 0
Accepted
time: 905ms
memory: 167320kb
input:
1 1000000 6 1991827 13 8125243 19 22493 24 4282711 28 356362 39 765152 41 6737899 44 8549464 57 4530192 64 7201376 67 6695629 70 3830504 70 6658581 71 4591382 71 8349070 75 2107828 76 4073563 81 2712838 92 1391185 95 4663781 102 5986957 113 8423636 118 7826607 122 1171556 122 3118750 160 938066 162 ...
output:
9609125
result:
ok single line: '9609125'
Test #5:
score: -100
Time Limit Exceeded
input:
1 1000000 108 565196036 597 561009880 1007 831705109 2597 55966094 2869 765993518 3025 202191673 3283 237167825 3410 829643653 4879 960747182 7284 679152790 8765 64201585 8899 97619554 9320 713144607 9519 991746776 9913 346063307 11161 970513525 11256 975123550 12073 778562963 14286 206857559 15803 ...
output:
268764694