| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1238955 | noop | Hack (APIO25_hack) | C++20 | 0 ms | 0 KiB |
// #include "hack.h"
#include <bits/stdc++.h>
using namespace std;
static int n = 0;
static int total_cost = 0;
long long collisions(std::vector<long long> x){
total_cost += (int) x.size();
if (total_cost > 1000000){
printf("Total cost exceeded 1,000,000\n");
exit(0);
}
long long res = 0;
std::map<int, int> table;
std::set<long long> seen;
for (long long v : x){
if (v < 1 || v > (long long)1e18){
printf("x[i] is out of range\n");
exit(0);
}
if (seen.find(v) != seen.end()){
printf("x has a duplicate element\n");
exit(0);
}
seen.insert(v);
res += table[v % n];
table[v % n]++;
}
return res;
}
bool query (int l, int r){
int gap=sqrt(r-l+1);
vector<long long> v;
for (int i=1; i<=gap; ++i)
v.push_back(i);
for (int i=r+1; i>l+gap; i-=gap)
v.push_back(i);
return collisions(v);
}
int hack(){
int l=1,r=1000000000;
while (l<r){
int mid=l+r>>1;
if (query(l,mid))
r=mid;
else
l=mid+1;
}
return l;
}
int main(){
int t;
assert(1 == scanf("%d", &t));
std::vector<int> ns(t);
for (int i = 0; i < t; i++){
assert(1 == scanf("%d", &ns[i]));
}
for (int i = 0; i < t; i++){
total_cost = 0;
n = ns[i];
int ans = hack();
printf("%d %d\n", ans, total_cost);
}
return 0;
}