Submission #1238955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238955		noop	Hack (APIO25_hack)	C++20	Compilation error	0 ms	0 KiB

hack

// #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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccOpGOTV.o: in function `collisions(std::vector<long long, std::allocator<long long> >)':
grader.cpp:(.text+0x470): multiple definition of `collisions(std::vector<long long, std::allocator<long long> >)'; /tmp/ccTbld0o.o:hack.cpp:(.text+0x460): first defined here
/usr/bin/ld: /tmp/ccOpGOTV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccTbld0o.o:hack.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status