Tenka1 Programmer Contest

Submission #1642764

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <memory.h>
#include <random>
#include <set>
#include <stdint.h>
#include <vector>
using namespace std;

typedef pair<pair<int, int>, int> line;

template <typename T>
pair<T, T> cross(const line& l1, const line& l2)
{
    const int a1 = l1.first.first;
    const int b1 = l1.first.second;
    const int c1 = l1.second;

    const int a2 = l2.first.first;
    const int b2 = l2.first.second;
    const int c2 = l2.second;

    const T x = (T)(c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);
    const T y = (T)(c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1);

    return make_pair(x, y);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<line> vs(n);
    for (auto& p : vs) {
        cin >> p.first.first >> p.first.second >> p.second;
    }

    mt19937 rng(time(nullptr));
    uniform_int_distribution<int> dist(0, n - 1);

    vector<double> xs, ys;
    const int SAMPLES = 500000;

    for (int t = 0; t < SAMPLES; t++) {
    _rep:
        int i = dist(rng);
        int j = dist(rng);
        if (i == j)
            goto _rep;

        auto p = cross<double>(vs[i], vs[j]);
        xs.push_back(p.first);
        ys.push_back(p.second);
    }

    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());

    double d_lo_x = xs[SAMPLES / 2 - SAMPLES / 500];
    double d_hi_x = xs[SAMPLES / 2 + SAMPLES / 500];
    double d_lo_y = ys[SAMPLES / 2 - SAMPLES / 500];
    double d_hi_y = ys[SAMPLES / 2 + SAMPLES / 500];

    bool determ_x = (d_lo_x == d_hi_x);
    bool determ_y = (d_lo_y == d_hi_y);

    float lo_x = d_lo_x;
    float hi_x = d_hi_x;
    float lo_y = d_lo_y;
    float hi_y = d_hi_y;

    int lo_cnt_x = 0;
    int lo_cnt_y = 0;

    vector<double> rxs, rys;

    static int fs[40000];
    for (int i = 0; i < n; i++) {
        line a = vs[i];

#pragma clang loop vectorize(enable)
        for (int j = i + 1; j < n; j++) {
            const auto p = cross<float>(a, vs[j]);

            if (p.first < lo_x)
                lo_cnt_x++;
            if (p.second < lo_y)
                lo_cnt_y++;

            fs[j] = (lo_x <= p.first && p.first <= hi_x ? 1 : 0) | (lo_y <= p.second && p.second <= hi_y ? 2 : 0);
        }

        if (!determ_x) {
            for (int j = i + 1; j < n; j++) {
                if (fs[j] & 1) {
                    rxs.push_back(cross<double>(vs[i], vs[j]).first);
                }
            }
        }
        if (!determ_y) {
            for (int j = i + 1; j < n; j++) {
                if (fs[j] & 2) {
                    rys.push_back(cross<double>(vs[i], vs[j]).second);
                }
            }
        }
    }

    int nn = (n * (n - 1) / 2 + 1) / 2;
    // cerr << lo_cnt_x << " + " << rxs.size() << " = " << lo_cnt_x + rxs.size() << " ~ " << nn << endl;
    // cerr << lo_cnt_y << " + " << rys.size() << " = " << lo_cnt_y + rys.size() << " ~ " << nn << endl;

    assert(determ_x || (lo_cnt_x < nn && lo_cnt_x + rxs.size() >= nn));
    assert(determ_y || (lo_cnt_y < nn && lo_cnt_y + rys.size() >= nn));

    if (!determ_x)
        nth_element(rxs.begin(), rxs.begin() + (nn - 1 - lo_cnt_x), rxs.end());
    if (!determ_y)
        nth_element(rys.begin(), rys.begin() + (nn - 1 - lo_cnt_y), rys.end());

    printf("%.12f %.12f\n",
        determ_x ? d_lo_x : rxs[nn - 1 - lo_cnt_x],
        determ_y ? d_lo_y : rys[nn - 1 - lo_cnt_y]);

    return 0;
}

Submission

Task問題 E - CARtesian Coodinate
User nameユーザ名 tanakh
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 800
Source lengthソースコード長 3646 Byte
File nameファイル名
Exec time実行時間 4913 ms
Memory usageメモリ使用量 70344 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - s1.txt,s2.txt,s3.txt
All 800 / 800 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,30.txt,31.txt,32.txt,s1.txt,s2.txt,s3.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt AC 4905 ms 69192 KB
02.txt AC 4897 ms 61468 KB
03.txt AC 4913 ms 63772 KB
04.txt AC 4892 ms 60680 KB
05.txt AC 4899 ms 60788 KB
06.txt AC 4872 ms 60876 KB
07.txt AC 4906 ms 70344 KB
08.txt AC 4904 ms 68300 KB
09.txt AC 4882 ms 60880 KB
10.txt AC 4890 ms 67404 KB
11.txt AC 4903 ms 61456 KB
12.txt AC 4899 ms 68812 KB
13.txt AC 4905 ms 69448 KB
14.txt AC 4902 ms 61912 KB
15.txt AC 4889 ms 61600 KB
16.txt AC 4906 ms 68940 KB
17.txt AC 4902 ms 68044 KB
18.txt AC 4909 ms 61156 KB
19.txt AC 4892 ms 60960 KB
20.txt AC 4897 ms 59764 KB
21.txt AC 3410 ms 10972 KB
22.txt AC 3408 ms 8924 KB
23.txt AC 4885 ms 66508 KB
24.txt AC 4883 ms 65484 KB
25.txt AC 4876 ms 66892 KB
26.txt AC 4884 ms 61020 KB
27.txt AC 111 ms 8800 KB
28.txt AC 104 ms 8284 KB
29.txt AC 111 ms 8284 KB
30.txt AC 88 ms 8284 KB
31.txt AC 78 ms 10336 KB
32.txt AC 111 ms 8284 KB
s1.txt AC 105 ms 8284 KB
s2.txt AC 87 ms 8284 KB
s3.txt AC 89 ms 8284 KB