QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #425301 | #7277. Bring Down the | Lynkcat | 10 | 90ms | 4188kb | C++20 | 1.9kb | 2024-05-30 07:58:20 | 2024-05-30 07:58:20 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N
using namespace std;
int S,Q;
map<tuple<int,int,int,int>,bool>Mp;
inline int dfs(int x,int y,int a,int b)
{
if (x<=0) return 0;
if (a<=0) return 1;
if (x<=1ll*b*S&&a<=1ll*y*S)
{
ll t=min(-x+1ll*b*S,-a+1ll*y*S)/S+1;
b-=t,y-=t;
}
if (x<=1ll*b*S && a-1ll*y*S>=S) return 0;
if (x-1ll*b*S>=S&&a-1ll*y*S<=S) return 1;
if (x<=1ll*b*S&&y==0)
{
ll t=(-x+1ll*b*S)/(S-1ll*(a-1ll*y*S))+1;
if (1ll*(a-1ll*y*S)*t>=x) return 0;
x+=t*(-1ll*(a-1ll*y*S));
b-=t;
}
if (a-1ll*y*S>=S||a-1ll*y*S<=0)
{
return dfs(a-x+1ll*b*S,b,x,y)^1;
// return res;
}
if (x<=1ll*b*S)
{
return dfs(a,b-1,x,y)^1;
// return res;
}
if (Mp.count({x,y,a,b})) return Mp[{x,y,a,b}];
bool &res=Mp[{x,y,a,b}];
res=0;
if (x>1ll*b*S)
{
res=dfs(a-x+1ll*b*S,b,x,y)^1;
if (res)return res;
}
if (b>0)
{
res=dfs(a,b-1,x,y)^1;
if (res)return res;
}
return 0;
}
mt19937_64 rnd(time(0));
const int B=2000;
void BellaKira()
{
cin>>S>>Q;
while (Q--)
{
int x,y,a,b;
x=rnd()%B+1,y=rnd()%B+1,a=rnd()%B+1,b=rnd()%B+1;
cin>>x>>y>>a>>b;
if (dfs(x,y,a,b)) cout<<"YES\n";
else cout<<"NO\n";
// if (Q%1000==0)
// cerr<<Q<<" "<<sz(Mp)<<endl;
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3744kb
input:
17 2 42 1 33 1 42 1 33 7
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: 0
Accepted
time: 67ms
memory: 3788kb
input:
2 250000 75 16 56 55 50 9 49 60 18 67 62 5 30 54 61 39 22 39 42 31 26 30 55 1 23 30 53 16 55 13 6 44 69 8 58 72 53 7 60 12 29 14 26 34 37 64 24 71 19 3 40 1 64 13 33 65 67 24 68 3 64 17 50 66 71 6 62 13 15 29 26 24 51 30 34 45 46 5 40 72 54 52 60 49 35 21 18 30 39 31 35 34 30 74 72 5 74 12 6 15 11 4...
output:
NO NO YES YES NO YES NO NO NO YES NO NO NO NO YES NO YES NO NO NO YES NO NO YES YES NO YES YES NO YES YES NO NO YES NO NO YES YES YES NO NO NO NO YES YES YES YES NO YES NO YES NO YES YES YES YES YES NO NO NO YES NO NO NO YES YES NO YES NO YES NO YES YES YES YES NO YES YES YES NO YES NO NO NO NO YES ...
result:
ok 250000 token(s): yes count is 122161, no count is 127839
Test #3:
score: -5
Wrong Answer
time: 90ms
memory: 4136kb
input:
7 250000 14 72 33 41 43 64 63 62 34 14 69 9 19 75 21 57 47 6 43 53 19 53 58 46 50 49 49 74 30 75 53 68 36 42 53 14 70 40 52 73 70 44 75 44 38 75 72 46 11 45 20 10 25 67 35 60 54 27 14 28 53 35 26 44 10 20 60 13 61 2 41 6 54 3 66 8 43 34 69 31 52 16 3 41 53 62 33 66 15 75 27 32 73 22 22 44 66 15 56 1...
output:
YES NO YES YES NO YES NO YES YES NO YES YES YES YES YES NO NO YES NO YES NO NO YES NO NO YES NO YES NO YES NO YES YES YES YES YES NO YES YES NO YES YES NO YES YES NO NO YES NO NO NO YES NO YES YES NO NO NO NO NO YES NO YES YES YES NO YES YES NO NO NO NO NO YES YES NO YES NO YES NO NO YES NO NO NO NO...
result:
wrong answer expected NO, found YES [291st token]
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 10
Accepted
Test #28:
score: 10
Accepted
time: 82ms
memory: 3728kb
input:
1 250000 554333015044 833858497873 833858497874 554333015044 655160857180 306396306924 306396306917 655160857187 374728598365 176680698490 176680698490 374728598365 764650258714 835600427315 835600427309 764650258720 521594231110 318048536486 318048536482 521594231115 273627794040 449769302710 10899...
output:
NO YES YES YES NO NO NO NO NO NO YES YES YES YES YES NO NO NO YES YES YES YES YES NO YES NO NO YES YES YES NO NO YES YES YES YES NO NO YES YES YES NO NO YES NO YES YES YES NO YES NO NO NO YES NO NO NO YES NO NO NO YES YES YES YES YES NO YES NO YES YES NO NO NO YES NO YES NO NO NO YES YES NO NO YES N...
result:
ok 250000 token(s): yes count is 126293, no count is 123707
Test #29:
score: 0
Accepted
time: 80ms
memory: 3724kb
input:
1 250000 129596328651 633211431893 1 762807760544 1 983509496641 151077576062 229908055916 36498040145 186033440917 1 995620003790 247250323075 720548396611 720548396605 247250323082 464252981836 491098062545 12027035640 943324008741 719683599156 92798217394 1 812481816550 317330065824 621406415744 ...
output:
NO YES NO NO YES NO YES NO NO NO NO NO NO YES YES NO NO YES YES YES NO YES YES NO NO YES YES NO NO YES YES NO YES NO YES NO NO YES YES YES NO YES YES NO YES NO YES YES YES YES NO NO YES YES YES NO NO YES YES NO YES YES NO YES NO YES YES YES NO NO YES NO YES NO NO YES YES YES NO NO NO NO YES YES NO N...
result:
ok 250000 token(s): yes count is 143356, no count is 106644
Test #30:
score: 0
Accepted
time: 86ms
memory: 3668kb
input:
1 250000 807680045522 377273608557 256372130241 928581523838 536035116725 716237980103 379308294473 872964802356 1 882064014033 529720193901 352343820133 80961796479 258174541326 183165451143 155970886662 739448494904 100650373373 75082626963 765016241315 166426307909 865864146065 703399919607 32889...
output:
YES NO YES YES NO NO NO NO YES YES NO YES YES NO NO NO NO YES YES NO YES NO YES NO NO YES NO YES NO NO YES NO NO NO NO NO NO NO YES NO YES YES YES NO NO NO NO NO YES YES YES YES NO YES NO YES YES NO NO YES NO YES NO NO YES NO YES YES YES NO NO NO YES NO NO YES YES YES NO NO YES YES YES YES NO NO NO ...
result:
ok 250000 token(s): yes count is 132783, no count is 117217
Test #31:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1 1 999999999999 999999999999 999999999999 999999999999
output:
YES
result:
ok YES
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #60:
score: 20
Accepted
time: 83ms
memory: 3780kb
input:
1 250000 554333015044 833858497873 833858497874 554333015044 655160857180 306396306924 306396306917 655160857187 374728598365 176680698490 176680698490 374728598365 764650258714 835600427315 835600427309 764650258720 521594231110 318048536486 318048536482 521594231115 273627794040 449769302710 10899...
output:
NO YES YES YES NO NO NO NO NO NO YES YES YES YES YES NO NO NO YES YES YES YES YES NO YES NO NO YES YES YES NO NO YES YES YES YES NO NO YES YES YES NO NO YES NO YES YES YES NO YES NO NO NO YES NO NO NO YES NO NO NO YES YES YES YES YES NO YES NO YES YES NO NO NO YES NO YES NO NO NO YES YES NO NO YES N...
result:
ok 250000 token(s): yes count is 126293, no count is 123707
Test #61:
score: -20
Wrong Answer
time: 75ms
memory: 4188kb
input:
33 250000 42 63 17 64 48 31 9 35 46 64 75 15 42 14 16 17 3 37 49 15 70 39 16 43 52 2 8 8 12 12 57 9 36 42 75 1 9 60 30 58 47 71 75 69 75 7 3 30 45 51 24 52 14 15 2 25 55 35 2 53 68 32 31 34 69 43 56 45 44 68 75 57 29 36 2 55 56 61 5 71 36 55 75 21 38 73 75 69 61 72 75 24 67 10 74 10 48 28 28 30 47 6...
output:
YES YES YES NO YES NO NO NO YES YES YES YES YES NO YES NO NO YES NO YES YES NO YES YES NO NO NO NO YES YES YES NO YES YES YES NO YES YES NO NO NO NO YES YES YES NO NO YES NO NO NO NO YES NO NO NO NO YES NO NO NO YES YES YES YES YES NO NO YES NO NO NO YES NO YES NO NO NO YES NO NO YES NO YES YES NO Y...
result:
wrong answer expected YES, found NO [22nd token]
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%