QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#798993	#7253. Jump	Invincible	AC ✓	1730ms	58788kb	C++23	2.2kb	2024-12-04 20:09:29	2024-12-04 20:09:29

Judging History

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

[2024-12-04 20:09:29]
评测

测评结果：AC
用时：1730ms
内存：58788kb

查看

[2024-12-04 20:09:29]
提交

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
//#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;

//char buf[1<<20],*p1,*p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
	int s = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
	return f ? s : -s;
}
template<typename T>void chkmax(T&x,const T&y){x=max(x,y);}
template<typename T>void chkmin(T&x,const T&y){x=min(x,y);}

const int N=205;
int n,a[N],ansg[20005],ansf[20005];
bitset<40000>f[10005],g[10005];

bool Med;
signed main() {
	fprintf(stderr,"%.3lfMb\n",(&Mbe-&Med)/1024./1024.);
	n=read();
	rep(i,1,n)a[i]=read();
	f[0].set(20000);
	rep(i,1,5000){
		rep(j,1,n)g[i]|=f[i-1]<<a[j];
		rep(j,1,n)f[i]|=g[i]>>a[j];
	}
	memset(ansf,-1,sizeof ansf);
	memset(ansg,-1,sizeof ansg);
	rep(j,0,20000){
		ansg[j]=ansf[j]=-1;
		rep(i,0,5000){
			if(g[i][j+20000]){
				ansg[j]=i;
				break;
			}
		} 
		rep(i,0,5000){
			if(f[i][j+20000]){
				ansf[j]=i;
				break;
			}
		}
	}
	for(int Q=read();Q--;){
		int s=read(),t=read();
		if((s^t)&1){
			printf("-1\n");
			continue;
		}
		if(s>t)swap(s,t);
		if(!~ansf[(t-s)/2]&&!~ansg[(s+t)/2]){
			printf("-1\n");
			continue;
		}
		int ans=1e9;
		if(~ansf[(t-s)/2])ans=min(ans,ansf[(t-s)/2]*2);
		if(~ansg[(s+t)/2])ans=min(ans,ansg[(s+t)/2]*2-1);
		printf("%d\n",ans);
	}
	return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 65ms

memory: 56040kb

input:

output:

result:

ok 10 numbers

Test #2:

score: 0

Accepted

time: 58ms

memory: 55296kb

input:

output:

result:

ok 10 numbers

Test #3:

score: 0

Accepted

time: 1632ms

memory: 54952kb

input:

output:

result:

ok 100000 numbers

Test #4:

score: 0

Accepted

time: 1634ms

memory: 55580kb

input:

output:

result:

ok 100000 numbers

Test #5:

score: 0

Accepted

time: 1620ms

memory: 54904kb

input:

output:

result:

ok 100000 numbers

Test #6:

score: 0

Accepted

time: 1646ms

memory: 55712kb

input:

output:

result:

ok 100000 numbers

Test #7:

score: 0

Accepted

time: 1636ms

memory: 55360kb

input:

output:

result:

ok 100000 numbers

Test #8:

score: 0

Accepted

time: 1624ms

memory: 55224kb

input:

output:

result:

ok 100000 numbers

Test #9:

score: 0

Accepted

time: 1641ms

memory: 55984kb

input:

output:

result:

ok 100000 numbers

Test #10:

score: 0

Accepted

time: 1622ms

memory: 55968kb

input:

output:

result:

ok 100000 numbers

Test #11:

score: 0

Accepted

time: 1635ms

memory: 57072kb

input:

output:

result:

ok 100000 numbers

Test #12:

score: 0

Accepted

time: 1625ms

memory: 55064kb

input:

output:

result:

ok 100000 numbers

Test #13:

score: 0

Accepted

time: 1631ms

memory: 56332kb

input:

output:

-1
-1
2
2
2
-1
-1
-1
-1
2
2
2
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
2
-1
-1
-1
2
-1
2
-1
-1
-1
2
-1
2
-1
-1
-1
2
2
2
2
-1
2
-1
-1
-1
-1
2
-1
2
-1
2
2
-1
2
2
-1
-1
-1
2
-1
2
-1
-1
-1
2
2
2
2
-1
2
2
-1
-1
2
2
2
2
-1
-1
2
2
2
2
2
-1
2
-1
2
2
2
-1
2
2
-1
-1
-1
-1
2
-1
-1
1
-1
2
2
2
2
2
-1
-1
-1
2
-1
-1
1
2
-1...

result:

ok 100000 numbers

Test #14:

score: 0

Accepted

time: 1631ms

memory: 55160kb

input:

output:

2
-1
2
2
-1
2
-1
2
-1
2
-1
2
-1
-1
2
-1
2
-1
-1
-1
2
-1
-1
-1
2
2
2
-1
-1
-1
-1
2
-1
2
2
-1
-1
2
2
-1
2
-1
2
-1
2
-1
2
2
2
-1
-1
2
2
3
2
2
-1
2
2
2
-1
2
-1
2
2
2
2
2
-1
2
-1
2
2
-1
-1
-1
-1
-1
-1
2
2
2
2
-1
2
-1
2
-1
2
-1
-1
-1
2
-1
-1
-1
-1
-1
2
-1
2
2
2
-1
-1
-1
-1
2
-1
-1
-1
2
2
-1
2
-1
2
2
-1
-1...

result:

ok 100000 numbers

Test #15:

score: 0

Accepted

time: 1675ms

memory: 56140kb

input:

output:

result:

ok 100000 numbers

Test #16:

score: 0

Accepted

time: 199ms

memory: 55980kb

input:

output:

result:

ok 100000 numbers

Test #17:

score: 0

Accepted

time: 932ms

memory: 55844kb

input:

output:

result:

ok 100000 numbers

Test #18:

score: 0

Accepted

time: 1103ms

memory: 55688kb

input:

output:

result:

ok 100000 numbers

Test #19:

score: 0

Accepted

time: 1730ms

memory: 56456kb

input:

output:

result:

ok 100000 numbers

Test #20:

score: 0

Accepted

time: 129ms

memory: 58676kb

input:

1
2894
100000
1754 10
4480 5082
4672 2376
2601 2653
1480 4574
3486 1160
299 1157
3257 1455
4806 1934
3994 4586
4719 1853
2748 4692
3880 3790
1786 3710
1855 4071
637 865
420 524
1259 509
3643 1343
1516 3624
153 645
5538 5280
3294 3428
4165 2415
3428 3848
4058 2410
4328 5756
707 3955
5257 391
5387 190...

output:

-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
-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
-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
...

result:

ok 100000 numbers

Test #21:

score: 0

Accepted

time: 130ms

memory: 56536kb

input:

output:

-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
-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
-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
-...

result:

ok 100000 numbers

Test #22:

score: 0

Accepted

time: 35ms

memory: 56660kb

input:

output:

result:

ok 100000 numbers

Test #23:

score: 0

Accepted

time: 46ms

memory: 55988kb

input:

output:

result:

ok 100000 numbers

Test #24:

score: 0

Accepted

time: 60ms

memory: 58788kb

input:

output:

result:

ok 100000 numbers

Test #25:

score: 0

Accepted

time: 57ms

memory: 55404kb

input:

output:

result:

ok 100000 numbers

Test #26:

score: 0

Accepted

time: 71ms

memory: 56256kb

input:

7
73
202
360
488
906
1202
1293
100000
4174 4076
1401 4037
1652 3874
287 4319
5772 1690
1564 1592
2878 6080
4604 4348
5726 718
2601 455
2308 1694
1740 5866
2635 5379
2002 4792
3025 373
2731 2909
142 4744
4124 1754
1963 2521
441 2635
2098 420
4279 5115
5487 1339
2021 3063
1897 5411
1635 6063
5565 2271...

output:

result:

ok 100000 numbers

Test #27:

score: 0

Accepted

time: 80ms

memory: 55616kb

input:

output:

result:

ok 100000 numbers

Test #28:

score: 0

Accepted

time: 82ms

memory: 56484kb

input:

output:

result:

ok 100000 numbers

Test #29:

score: 0

Accepted

time: 96ms

memory: 56400kb

input:

output:

result:

ok 100000 numbers

Test #30:

score: 0

Accepted

time: 125ms

memory: 56060kb

input:

2
1517
2330
100000
8617 4901
5281 9927
8967 697
6975 7449
453 395
7637 6263
6089 2353
4338 3396
1382 7850
1965 8829
4276 5000
766 6562
2581 1869
3244 9360
4941 9847
8824 7238
9774 9652
4501 2183
1033 3539
2148 9706
4673 1011
7967 1713
315 8545
425 1491
6311 6963
6477 4479
6689 3457
345 3593
7510 597...

output:

-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
-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
-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
...

result:

ok 100000 numbers

Test #31:

score: 0

Accepted

time: 128ms

memory: 55916kb

input:

output:

-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
-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
-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
...

result:

ok 100000 numbers

Test #32:

score: 0

Accepted

time: 129ms

memory: 56012kb

input:

output:

-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
-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
-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
...

result:

ok 100000 numbers

Test #33:

score: 0

Accepted

time: 122ms

memory: 56212kb

input:

output:

-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
-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
-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
...

result:

ok 100000 numbers

Test #34:

score: 0

Accepted

time: 120ms

memory: 55284kb

input:

2
4115
8634
100000
5662 1954
4520 476
3649 8939
9387 5379
8625 3389
454 9482
8062 5270
2298 3902
7523 6829
9968 3860
2524 4442
9245 3117
4727 3393
2328 5784
9404 154
7098 840
9902 7910
9610 7176
7869 7865
9438 4490
0 7334
2039 4533
2167 9915
4488 5024
8199 8183
9195 3223
4586 4104
7982 8820
7994 894...

output:

-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
-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
-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
...

result:

ok 100000 numbers

Test #35:

score: 0

Accepted

time: 106ms

memory: 58712kb

input:

output:

result:

ok 100000 numbers

Test #36:

score: 0

Accepted

time: 112ms

memory: 55704kb

input:

output:

result:

ok 100000 numbers