QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#814935 | #9832. If I Could Turn Back Time | Wzy# | WA | 7ms | 3836kb | C++14 | 1.7kb | 2024-12-14 22:59:46 | 2024-12-14 22:59:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e5+10,M=2*N;
const int mod=998244353;
const LL P=1e9+7;
const LL INF=1e18;
int h[N],e[M],ne[M],w[M],idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];
int T=1;
int d[N][2];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++ ;
} while (y != u);
}
}
void solve(){
int n;
cin>>n;
LL res=0;
vector<int> h(n),p(n);
for(int i=0;i<n;i++) cin>>h[i];
for(int i=0;i<n;i++) cin>>p[i];
vector<PII> q;
for(int i=0;i<n;i++){
if(h[i]>p[i]){
cout<<-1<<endl;
return;
}
q.push_back({p[i]-h[i],p[i]});
}
sort(q.begin(),q.end());
for(int i=1;i<n;i++){
if(q[i].second<q[i-1].second){
cout<<-1<<endl;
return;
}
}
cout<<q[n-1].first<<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//int T=1;
cin>>T;
//T=10000;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
4 4 3 2 4 2 5 3 6 2 1 10 100000 5 1 2 3 4 5 1 2 3 4 5 3 1 4 6 4 1 8
output:
2 99990 0 -1
result:
ok 4 number(s): "2 99990 0 -1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
10 1 1 2 2 2 7 2 7 1 6 8 1 1 1 1 3 8 2 4 4 9 7 4 5 5 5 5 8 6 6 6 2 3 3 10 3 2 6 1 8 2 4 4 6 8 9 4 7 9 10
output:
1 0 2 0 5 5 3 7 2 1
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
100 1 4 9 2 57 42 67 52 2 9 53 13 68 1 5 10 1 11 41 1 4 8 1 7 16 5 1 12 66 2 14 33 21 83 11 29 1 20 22 2 29 67 59 98 4 1 12 85 1 26 16 98 5 1 4 47 5 8 8 37 40 58 11 31 54 66 89 2 22 12 75 63 1 10 10 1 34 37 7 7 16 21 62 3 16 1 9 46 55 96 4 44 2 1 4 24 4 2 1 23 18 29 28 82 68 4 73 77 66 6 80 84 72 8 ...
output:
5 10 15 5 30 4 9 -1 2 31 -1 43 -1 53 0 3 34 20 59 7 -1 -1 50 33 14 51 -1 47 3 90 23 19 0 35 13 17 51 -1 84 -1 16 85 6 32 28 -1 24 3 36 -1 45 -1 13 9 10 22 -1 33 13 -1 9 42 -1 17 45 26 68 32 8 -1 6 13 23 18 68 3 -1 59 -1 20 3 55 -1 4 -1 92 10 7 18 59 11 51 55 3 -1 42 14 39 28 -1
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
1000 1 295 730 1 562 588 1 440 834 2 170 150 739 630 1 308 536 1 11 432 2 302 1 345 47 1 26 48 2 79 433 85 927 1 194 563 1 95 289 1 129 481 1 2 76 2 942 297 984 343 1 26 309 3 342 236 182 898 833 706 3 949 1 1 990 142 142 1 350 377 1 489 554 2 603 617 750 999 2 86 60 454 308 1 349 873 2 3 124 11 258...
output:
435 26 394 569 228 421 -1 22 494 369 194 352 74 -1 283 -1 -1 27 65 382 368 524 134 136 399 20 -1 317 76 -1 11 117 248 -1 747 234 39 257 -1 243 161 28 410 -1 219 402 517 0 -1 383 -1 -1 560 -1 150 283 69 -1 5 679 736 -1 178 241 6 154 250 7 152 521 -1 510 -1 253 689 152 163 455 7 -1 -1 -1 -1 127 58 138...
result:
ok 1000 numbers
Test #5:
score: -100
Wrong Answer
time: 7ms
memory: 3612kb
input:
10000 3 1 2 3 1 2 3 3 4 2 3 2 4 3 4 1 2 2 1 1 2 2 3 4 2 3 2 3 2 2 1 1 4 1 2 3 2 2 3 3 2 3 1 1 1 4 2 1 4 3 2 1 1 2 3 3 1 4 3 1 3 3 1 3 3 2 3 4 4 1 2 3 1 4 1 2 2 3 1 2 2 2 4 3 2 3 2 2 3 1 2 3 2 1 1 3 3 1 4 2 1 1 2 1 1 1 1 4 1 3 1 3 2 1 2 2 3 1 4 2 3 1 4 3 1 2 2 1 1 1 3 4 4 4 1 3 4 4 3 3 1 3 1 3 1 1 3 ...
output:
0 -1 2 -1 -1 3 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 1 -1 -1 3 -1 3 2 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 2 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 2 -1 ...
result:
wrong answer 3rd numbers differ - expected: '-1', found: '2'