Submission #976785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976785	2024-05-07T06:19:03 Z	AIF_is_carving	Strange Device (APIO19_strange_device)	C++17	15 / 100	5000 ms	524288 KB

strange_device

#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;

void solve(){

    set<pair<ll, ll>> s;
    ll n, A, B; cin>>n>>A>>B;
    if(n>1){
        for(int i=0; i<n; i++){
            ll x, y; cin>>x>>y;
            for(ll t = x; t<=y; t++){
                ll p = (t+(t/B))%A;
                ll q = t%B;

                s.insert({p,q});
            }
        }

        cout<<s.size()<<"\n";
    }
    else{
        //ll n, A, B; cin>>n>>A>>B;
        ll x, y; cin>>x>>y;
        ll X = A/(gcd(B+1, A));

        ll t;

        int powX=0, powB=0;
        ll xxx = X;
        while(xxx>0){
            xxx/=2;
            powX+=1;
        }
        xxx=B;
        while(xxx>0){
            xxx/=2;
            powB+=1;
        }

        if(powB+powX>61) t=2e18;
        else t = B*X;

        cout<<min<ll>(y-x+1, t)<<"\n";

    }
    

    return;

}

int main(){   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t=1; //cin>>t;

    while(t--){
        solve();
    }

    return 0;

}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	35 ms	12300 KB	Output is correct
3	Correct	62 ms	18004 KB	Output is correct
4	Correct	2 ms	856 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	6 ms	1116 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	428 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	31 ms	7128 KB	Output is correct
16	Correct	21 ms	6748 KB	Output is correct
17	Correct	47 ms	6708 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #3
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	113 ms	32328 KB	Output is correct
3	Correct	150 ms	32080 KB	Output is correct
4	Correct	102 ms	30500 KB	Output is correct
5	Execution timed out	5033 ms	62548 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	400 ms	63036 KB	Output is correct
3	Runtime error	1535 ms	524288 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	400 ms	63036 KB	Output is correct
3	Runtime error	1535 ms	524288 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	400 ms	63036 KB	Output is correct
3	Runtime error	1535 ms	524288 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Runtime error	1373 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	35 ms	12300 KB	Output is correct
3	Correct	62 ms	18004 KB	Output is correct
4	Correct	2 ms	856 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	6 ms	1116 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	428 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	31 ms	7128 KB	Output is correct
16	Correct	21 ms	6748 KB	Output is correct
17	Correct	47 ms	6708 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	113 ms	32328 KB	Output is correct
26	Correct	150 ms	32080 KB	Output is correct
27	Correct	102 ms	30500 KB	Output is correct
28	Execution timed out	5033 ms	62548 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Submission #976785

Compilation message