CSES - Aalto Competitive Programming 2024 - wk10 - Wed

CSES - Aalto Competitive Programming 2024 - wk10 - Wed - Results

Submission details
Task:	Closest points
Sender:	aalto2024k_007
Submission time:	2024-11-14 01:28:20 +0200
Language:	C++ (C++17)
Status:	READY
Result:	TIME LIMIT EXCEEDED

Test results
test	verdict	time
#1	ACCEPTED	0.01 s	details
#2	TIME LIMIT EXCEEDED	--	details
#3	TIME LIMIT EXCEEDED	--	details
#4	TIME LIMIT EXCEEDED	--	details
#5	ACCEPTED	0.00 s	details
#6	TIME LIMIT EXCEEDED	--	details
#7	ACCEPTED	0.00 s	details
#8	ACCEPTED	0.00 s	details
#9	ACCEPTED	0.00 s	details
#10	TIME LIMIT EXCEEDED	--	details
#11	ACCEPTED	0.00 s	details
#12	ACCEPTED	0.00 s	details
#13	TIME LIMIT EXCEEDED	--	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.01 s	details
#16	TIME LIMIT EXCEEDED	--	details
#17	TIME LIMIT EXCEEDED	--	details
#18	ACCEPTED	0.00 s	details

Code

#include <bits/stdc++.h>

using namespace std;

#define debug(...) Debug(#__VA_ARGS__, __VA_ARGS__);
template <typename... Args>
void Debug(const char* names, Args&&... args) {
   std::cerr << names << " = ";
   ((std::cerr << args << ", "), ...) << "\b\b " << std::endl;
}
#define ll long long
#define ull unsigned long long
#define vi vector<int>

ull distance2(const pair<ll,ll>& p1, const pair<ll,ll>& p2) {
    ll x1 = p1.first, y1 = p1.second;
    ll x2 = p2.first, y2 = p2.second;
    ull dx = (ull) abs(x1 - x2);
    ull dy = (ull) abs(y1 - y2);
    return dx*dx + dy*dy;
}

int main() {
    int n;
    cin >> n;

    vector<pair<ll,ll>> points (n);
    for (int i = 0; i < n; i++)
    {
        cin >> points[i].first >> points[i].second;
    }

    sort(points.begin(), points.end());

    ull min_d2 = ULLONG_MAX;
    for (int i = 0; i < n; i++)
    {
        int iback = i-1;
        debug(i)
        while (iback >= 0) {
            ull d2 = distance2(points[i], points[iback]);
            ull dx2 = (points[i].first - points[iback].first)*(points[i].first - points[iback].first);
            if (d2 < min_d2) min_d2 = d2;
            if (dx2 > min_d2) break;
            iback--;
        }
    }
    
    cout << min_d2 << endl;
    

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`100 58 36 81 -7 46 49 87 -58 ...` view save

correct output
`1` view save

user output
`1` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,  
i = 4,  
i = 5,  
i = 6,  
i = 7,  
i = 8,  
i = 9,  
i = 10,  
i = 11,  
i = 12,  
i = 13,  
i = 14,  
i = 15,  
i = 16,  
i = 17,  
i = 18,  
i = 19,  
i = 20,  
i = 21,  
i = 22,  
i = 23,  
i = 24,  
i = 25,  
i = 26,  
i = 27,  
i = 28,  
i = 29,  
i = 30,  
i = 31,  
i = 32,  
i = 33,  
i = 34,  
i = 35,  
i = 36,  
i = 37,  
i = 38,  
i = 39,  
i = 40,  
i = 41,  
i = 42,  
i = 43,  
i = 44,  
i = 45,  
i = 46,  
i = 47,  
i = 48,  
i = 49,  
i = 50,  
i = 51,  
i = 52,  
i = 53,  
i = 54,  
i = 55,  
i = 56,  
i = 57,  
i = 58,  
i = 59,  
i = 60,  
i = 61,  
i = 62,  
i = 63,  
i = 64,  
i = 65,  
i = 66,  
i = 67,  
i = 68,  
i = 69,  
i = 70,  
i = 71,  
i = 72,  
i = 73,  
i = 74,  
i = 75,  
i = 76,  
i = 77,  
i = 78,  
i = 79,  
i = 80,  
i = 81,  
i = 82,  
i = 83,  
i...

Test 2

Verdict: TIME LIMIT EXCEEDED

input
`200000 -222 -705 277 680 -436 561 528 -516 ...` view save

correct output
`1` view save

user output
(empty)

Test 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 -464738043 865360844 465231470 129093134 -276549869 -21946314 111055008 -48821736 ...` view save

correct output
`25413170` view save

user output
(empty)

Test 4

Verdict: TIME LIMIT EXCEEDED

input
`200000 1 513001000 2 689002000 3 785003000 4 799004000 ...` view save

correct output
`1000000` view save

user output
(empty)

Test 5

Verdict: ACCEPTED

input
`4 0 0 0 3 3 0 1 1` view save

correct output
`2` view save

user output
`2` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,

Test 6

Verdict: TIME LIMIT EXCEEDED

input
`200000 1 0 1 1 1 2 1 3 ...` view save

correct output
`1` view save

user output
(empty)

Test 7

Verdict: ACCEPTED

input
`4 1 2 10 3 3 5 8 5` view save

correct output
`8` view save

user output
`8` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,

Test 8

Verdict: ACCEPTED

input
`4 10 6 4 10 8 3 2 3` view save

correct output
`13` view save

user output
`13` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,

Test 9

Verdict: ACCEPTED

input
`2 -999999999 -999999999 999999999 999999999` view save

correct output
`7999999984000000008` view save

user output
`7999999984000000008` view save

Error:

i = 0,  
i = 1,

Test 10

Verdict: TIME LIMIT EXCEEDED

input
`200000 0 1 1 1 2 1 3 1 ...` view save

correct output
`1` view save

user output
(empty)

Test 11

Verdict: ACCEPTED

input
`8 1 10000 -1 -10000 2 0 -2 0 ...` view save

correct output
`16` view save

user output
`16` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,  
i = 4,  
i = 5,  
i = 6,  
i = 7,

Test 12

Verdict: ACCEPTED

input
`3 -1000000000 -1000000000 1000000000 1000000000 0 0` view save

correct output
`2000000000000000000` view save

user output
`2000000000000000000` view save

Error:

i = 0,  
i = 1,  
i = 2,

Test 13

Verdict: TIME LIMIT EXCEEDED

input
`199999 1 1 2 1 3 1 4 1 ...` view save

correct output
`1` view save

user output
(empty)

Test 14

Verdict: ACCEPTED

input
`4 0 0 5 8 6 1 10000 0` view save

correct output
`37` view save

user output
`37` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,

Test 15

Verdict: ACCEPTED

input
`435 -842 -199 -480 798 -176 -406 792 608 ...` view save

correct output
`2` view save

user output
`2` view save

Error:

i = 0,  
i = 1,  
i = 2,  
i = 3,  
i = 4,  
i = 5,  
i = 6,  
i = 7,  
i = 8,  
i = 9,  
i = 10,  
i = 11,  
i = 12,  
i = 13,  
i = 14,  
i = 15,  
i = 16,  
i = 17,  
i = 18,  
i = 19,  
i = 20,  
i = 21,  
i = 22,  
i = 23,  
i = 24,  
i = 25,  
i = 26,  
i = 27,  
i = 28,  
i = 29,  
i = 30,  
i = 31,  
i = 32,  
i = 33,  
i = 34,  
i = 35,  
i = 36,  
i = 37,  
i = 38,  
i = 39,  
i = 40,  
i = 41,  
i = 42,  
i = 43,  
i = 44,  
i = 45,  
i = 46,  
i = 47,  
i = 48,  
i = 49,  
i = 50,  
i = 51,  
i = 52,  
i = 53,  
i = 54,  
i = 55,  
i = 56,  
i = 57,  
i = 58,  
i = 59,  
i = 60,  
i = 61,  
i = 62,  
i = 63,  
i = 64,  
i = 65,  
i = 66,  
i = 67,  
i = 68,  
i = 69,  
i = 70,  
i = 71,  
i = 72,  
i = 73,  
i = 74,  
i = 75,  
i = 76,  
i = 77,  
i = 78,  
i = 79,  
i = 80,  
i = 81,  
i = 82,  
i = 83,  
i...

Test 16

Verdict: TIME LIMIT EXCEEDED

input
`200000 1 0 1 2 1 4 1 6 ...` view save

correct output
`4` view save

user output
(empty)

Test 17

Verdict: TIME LIMIT EXCEEDED

input
`200000 0 1 2 1 4 1 6 1 ...` view save

correct output
`4` view save

user output
(empty)

Test 18

Verdict: ACCEPTED

input
`3 -1000000000 -1000000000 1000000000 1000000000 1000000000 -1000000000` view save

correct output
`4000000000000000000` view save

user output
`4000000000000000000` view save

Error:

i = 0,  
i = 1,  
i = 2,

Aalto Competitive Programming 2024 - wk10 - Wed

Closest points

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Tasks

Submissions (aalto2024k_007)