|

General

# Author Problem Lang Verdict Time Memory Sent Judged
55478889 Practice:
McDic
1182F - 45 GNU C++17 Accepted 780 ms 1288 KB 2019-06-12 06:15:32 2019-06-17 13:34:52
→ Source
#include <stdio.h>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>

typedef long long int lld;
const lld infL = 1LL << 60;

// Find x that abs(sin(p/q pi x)) is the largest in [start, end).
int solve(lld start, lld end, lld p, lld q){

// Construct base intervals
lld interval = 1;
while(interval * interval < end - start) interval++;

// Period is q/p. x should be the closest to the middle of period(q/2p).
// x % (2q/2p) should be the closest to q/2p => 2px % 2q should be the closest to q.
// Construct remainders
std::vector<std::pair<lld, lld>> remainders, remainders_copy;
for(lld i=start; i<start+interval; i++){
lld key = 2*p*i % (2*q);
remainders.push_back({key, i});
}
std::sort(remainders.begin(), remainders.end());
remainders_copy = remainders; remainders.clear();
remainders.push_back(remainders_copy[0]);
for(int i=1; i<remainders_copy.size(); i++){
if(remainders_copy[i].first != remainders_copy[i-1].first)
remainders.push_back(remainders_copy[i]);
} remainders_copy.clear();

// Look in [start + i*interval, start + (i+1)*interval), start + (i+1)*interval <= end.
// x + i*interval ~= q/2p => x ~= q/2p - i*interval.
//printf("base interval = %lld\n", interval);
for(iteration = 0; start + (iteration+1)*interval <= end; iteration++){
lld look = q - iteration * interval * 2 * p; // iteration * interval <= interval^2 <= end - start <= 10^8
look %= (2*q); if(look < 0) look += 2*q;
//printf("Looking %lld in [%lld, %lld)\n", look, start + iteration*interval, start + (iteration+1)*interval);
lld baseindex = std::lower_bound(remainders.begin(), remainders.end(), std::make_pair(look, -infL)) - remainders.begin();
for(int j=0; j>=-1; j--){
lld thisindex = (baseindex+j) % remainders.size(); if(thisindex < 0) thisindex += remainders.size();
lld thisvalue = remainders[thisindex].second + iteration * interval;
lld thisdistance = look - remainders[thisindex].first;
if(thisdistance < 0) thisdistance *= -1;
if(thisdistance > q) thisdistance = 2*q - thisdistance;
//printf("  Looking baseindex = %lld, thisindex = %lld, thisfirst = %lld, thisvalue = %lld (distance %lld)\n",
//	baseindex, thisindex, thisvalue, remainders[thisindex].first, thisdistance);
}
}
}

// Brute force for remaining ranges
for(lld v = start + iteration * interval; v < end; v++){
//printf("Looking %lld\n", v);
lld thisdistance = (2*p*v) % (2*q) - q; if(thisdistance < 0) thisdistance *= -1;
}
}

}

int main(void){
int testcases; scanf("%d", &testcases);
for(int t=0; t<testcases; t++){
lld a, b, p, q; scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
//printf("Case #%d: ", t+1);
printf("%d\n", solve(a, b+1, p, q));
}
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?