QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425385#7277. Bring Down the Sky Grading ServerLynkcat10 84ms3884kbC++203.4kb2024-05-30 10:13:282024-05-30 10:13:29

Judging History

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

  • [2024-05-30 10:13:29]
  • 评测
  • 测评结果:10
  • 用时:84ms
  • 内存:3884kb
  • [2024-05-30 10:13:28]
  • 提交

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;
map<tuple<int,int,int>,int>Mx;
inline int dfs(int x,int y,int a,int b);
inline int calc(int Y,int y,int b)
{
    if (Mx.count({Y,y,b})) return Mx[{Y,y,b}];
    int a=Y+y*S;
    int l=1,r=1e12;
    int &res=Mx[{Y,y,b}];
    res=0;
    while (l<=r)
    {
        int x=l+(r-l)/2;
        int nw=0;
        {
            if (b&&y) nw|=dfs(x,y-1,a,b-1);
            if (b&&a-y*S>0) nw|=dfs(x-(a-y*S),y,a,b-1);
        }
        {
            if (a-(x-b*S)<=0) nw=1;
            if (x-b*S>0&&y) nw|=dfs(x,y-1,a-(x-b*S),b);
            if (x-b*S>0&&a-y*S>0) nw|=dfs(x-(a-y*S),y,a-(x-b*S),b);
        }
        if (nw) 
        {
            res=x;
            r=x-1;
        } else l=x+1;
    }
    return res;
}
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 (b==0&&a-1ll*y*S<=0)
    {
        int t=min((a+x-1)/x,(y*S-a)/S+1);
        a-=t*x;
        if (a<=0) return 1;
        y-=t;
    }
    if (x<=1ll*b*S||b>0&&a-1ll*y*S<=0) 
    {
        return dfs(a,b-1,x,y)^1;
    }
    if (a-1ll*y*S>=S||b==0) 
    { 
        return dfs(a-x+1ll*b*S,b,x,y)^1;
    }
    ll X=x-1ll*b*S;
    ll Y=a-1ll*y*S;
    if ((__int128)(S-Y)*b>=(S-X)) return 1;
    if ((__int128)(S-X)*y+Y-X>=S) return dfs(a,b-1,x,y)^1;

    __int128 nw=(S-Y);
    if (nw>2*S) return 1;
    if (nw*y>2*S) return 1;if (y) nw*=y;
    if (nw*(b/2)>2*S) return 1;nw*=(b/2);
    if (nw*(b-b/2)>2*S) return 1;nw*=(b-b/2);

    if (x>=calc(Y,y,b)) return 1;
    return 0;

    // if (Mx.count({Y,y,b}))
    // {
    //     if (x<=Mx[{Y,y,b}]) return 0;
    // }
    // if (Mn.count({Y,y,b}))
    // {
    //     if (x>=Mn[{Y,y,b}]) return 1;
    // }
    // bool res;
    // res=0;
    // if (x>1ll*b*S)
    // {
    //     res=dfs(a-x+1ll*b*S,b,x,y)^1;
    // }
    // if (b>0)
    // {
    //     if (!res) 
    //         res=dfs(a,b-1,x,y)^1;
    // }
    // if (res==1) Mn[{Y,y,b}]=x;
    // else Mx[{Y,y,b}]=x;
    // return res;
}
mt19937_64 rnd(time(0));
const int B=1000000000000;
int ans[1000005];
void BellaKira()
{
    cin>>S>>Q;
    vector<tuple<int,int,int,int,int>>all;
    for (int i=1;i<=Q;i++)
    {
        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 (i%1000==0) cerr<<i<<" "<<sz(Mx)<<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: 3884kb

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: 5
Accepted
time: 47ms
memory: 3836kb

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
Accepted
time: 48ms
memory: 3760kb

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:

ok 250000 token(s): yes count is 123236, no count is 126764

Test #4:

score: 0
Wrong Answer
time: 50ms
memory: 3704kb

input:

42 250000
9 44 75 43
56 10 46 11
25 22 40 22
54 4 49 5
4 22 34 16
69 59 72 59
66 75 74 31
5 10 57 10
11 48 36 46
7 40 56 14
32 68 5 74
66 25 59 40
10 6 20 7
48 25 73 24
54 41 51 56
71 32 47 55
17 3 26 10
20 49 8 51
44 17 43 35
75 18 69 33
72 8 74 43
45 75 66 19
56 73 68 15
47 56 57 57
39 69 20 70
7 ...

output:

NO
NO
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
YES
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
NO
YES...

result:

wrong answer expected NO, found YES [56th token]

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 10
Accepted

Test #28:

score: 10
Accepted
time: 82ms
memory: 3756kb

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: 10
Accepted
time: 84ms
memory: 3700kb

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: 10
Accepted
time: 84ms
memory: 3756kb

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: 10
Accepted
time: 1ms
memory: 3704kb

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: 78ms
memory: 3812kb

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: 0
Wrong Answer
time: 51ms
memory: 3840kb

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
YES
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
NO
NO
NO
YES
NO
YES
YES
NO
Y...

result:

wrong answer expected YES, found NO [531st token]

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%