QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#239716#7680. Subwayucup-team1191#AC ✓1ms3848kbC++204.3kb2023-11-04 22:38:002023-11-04 22:38:01

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 22:38:01]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3848kb
  • [2023-11-04 22:38:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

// _________ vect (2D) ______________
template <typename T>
struct vect {
    T x = 0;
    T y = 0;

    vect() = default;
    vect(T x_, T y_) : x(x_), y(y_) {}

    inline T len2() const {
        return x * x + y * y;
    }

    inline ld len() const {
        return sqrtl(len2());
    }

    inline vect rotate() const {
        return vect(-y, x);
    }
};

template <typename T>
inline istream& operator>>(istream& in, vect<T>& v) {
    return in >> v.x >> v.y;
}

template <typename T>
inline ostream& operator<<(ostream& out, const vect<T>& v) {
    return out << "[" << v.x << "," << v.y << "]";
}

template <typename T>
inline vect<T> operator+(const vect<T>& a, const vect<T>& b) {
    return vect<T>(a.x + b.x, a.y + b.y);
}

template <typename T>
inline vect<T> operator-(const vect<T>& a, const vect<T>& b) {
    return vect<T>(a.x - b.x, a.y - b.y);
}

template <typename T>
inline vect<T> operator*(const vect<T>& a, T k) {
    return vect<T>(a.x * k, a.y * k);
}

template <typename T>
inline T operator*(const vect<T>& a, const vect<T>& b) {
    return a.x * b.x + a.y * b.y;
}

template <typename T>
inline T operator^(const vect<T>& a, const vect<T>& b) {
    return a.x * b.y - a.y * b.x;
}

bool check(vector<vect<ll>> v, vect<ll> base) {
    for (auto& t : v) {
        t = t - base;
    }
    sort(v.begin(), v.end(), [&](const auto& v1, const auto& v2) {
        return (v1 ^ v2) > 0;
    });
    for (int i = 0; i + 1 < (int)v.size(); i++) {
        if ((v[i] ^ v[i + 1]) == 0) {
            return false;
        }
    }
    return true;
}

mt19937 rnd(239);

void solve() {
    int n;
    cin >> n;
    vector<vect<ll>> v(n);
    vector<int> a(n);
    int mx = 0;
    int mnx = 0;
    int mny = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> a[i];
        mx = max(mx, a[i]);
        mnx = min(mnx, (int)v[i].x);
        mny = min(mny, (int)v[i].y);
    }
    cout << mx << "\n";
    mnx -= 1;
    mny -= 1;
    vect<ll> base;
    bool found = false;
    for (int sz = 1; !found; sz *= 2) {
        for (int it = 0; it < 10 && !found; it++) {
            int x = mnx - (rnd() % sz);
            int y = mny - (rnd() % sz);
            if (check(v, vect<ll>(x, y))) {
                base = vect<ll>(x, y);
                found = true;
                break;
            }
        }
    }

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return ((v[i] - base) ^ (v[j] - base)) > 0;
    });

    vector<vect<ll>> btw;
    btw.emplace_back(vect<ll>(1, 0) + v[order[0]] - base);
    for (int i = 0; i < n - 1; i++) {
        btw.emplace_back((v[order[i]] - base) + (v[order[i + 1]] - base));
    }
    btw.emplace_back(v[order.back()] + vect<ll>(0, 1));

    const int CS = 2;
    for (auto& t : btw) {
        t.x *= CS;
        t.y *= CS;
    }
    vector<vect<ll>> go;
    for (int i = 0; i < n; i++) {
        go.emplace_back(v[i] - base);
    }

    for (int it = 1; it <= mx; it++) {
        for (int i = 0; i < n; i++) {
            if (a[i] <= 0) {
                v[i] = v[i] + go[i];
            }
        }
        for (int i = 0; i < n; i++) {
            a[i]--;
        }
        vector<vect<ll>> pt;
        for (int i = 0; i < n; i++) {
            auto v1 = btw[i] * (ll) it + base;
            pt.emplace_back(v1);
            pt.emplace_back(v[order[i]]);
        }
/*#ifdef ONPC
        for (int i = 0; i + 1 < (int)pt.size(); i++) {
            cout << "Segment ";
            cout << pt[i].x << " " << pt[i].y << " ";
            cout << pt[i + 1].x << " " << pt[i + 1].y << "\n";
        }
        for (int i = 0; i < (int)pt.size(); i++) {
            cout << pt[i].x << " " << pt[i].y << "\n";
        }
#endif*/
        cout << pt.size() << " ";
        for (const auto& t : pt) {
            cout << t.x << " " << t.y << " ";
        }
        cout << "\n";
    }
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

input:

3
1 2 1
2 1 2
3 3 2

output:

2
6 7 3 2 1 13 11 3 3 11 13 1 2 
6 15 7 2 1 27 23 3 3 23 27 3 5 

result:

ok ok Sum L = 12

Test #2:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1
1 1 1

output:

1
2 5 3 1 1 

result:

ok ok Sum L = 2

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1
1 1 50

output:

50
2 5 3 1 1 
2 11 7 1 1 
2 17 11 1 1 
2 23 15 1 1 
2 29 19 1 1 
2 35 23 1 1 
2 41 27 1 1 
2 47 31 1 1 
2 53 35 1 1 
2 59 39 1 1 
2 65 43 1 1 
2 71 47 1 1 
2 77 51 1 1 
2 83 55 1 1 
2 89 59 1 1 
2 95 63 1 1 
2 101 67 1 1 
2 107 71 1 1 
2 113 75 1 1 
2 119 79 1 1 
2 125 83 1 1 
2 131 87 1 1 
2 137 91...

result:

ok ok Sum L = 100

Test #4:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

50
662 -567 48
728 -120 7
307 669 27
-885 -775 21
100 242 9
-784 -537 41
940 198 46
736 -551 30
-449 456 16
-945 382 18
-182 810 49
213 187 44
853 245 48
617 -305 19
-81 261 3
617 208 8
-548 -652 6
-888 -667 14
-371 -812 43
202 -702 10
-668 -725 5
961 -919 33
-870 -697 50
428 810 29
560 405 7
348 -3...

output:

50
100 2906 -918 961 -919 5536 -864 334 -893 3002 -820 -306 -897 1592 -658 -371 -812 2608 -268 202 -702 4674 222 662 -567 5742 524 736 -551 5652 1048 617 -305 3256 712 -462 -719 3714 996 846 -163 5334 1790 348 -322 5412 2002 885 -57 6172 2406 728 -120 5414 2170 506 -175 5838 2806 940 198 3730 1852 -...

result:

ok ok Sum L = 5000

Test #5:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

50
-772 697 1
-756 -909 1
659 923 1
850 471 1
260 -24 1
473 -639 1
-575 393 1
-466 197 1
333 -637 1
-192 -890 1
103 546 1
749 -723 1
-573 613 1
214 -138 1
277 928 1
266 291 1
911 275 1
-680 -67 1
69 190 1
-197 -795 1
684 618 1
729 -115 1
-658 -229 1
-595 -470 1
898 -172 1
401 81 1
133 685 1
223 400 ...

output:

1
100 451 -958 -162 -959 2055 -776 30 -869 1995 -638 -192 -890 3433 -346 749 -723 4763 156 473 -639 2871 12 -197 -795 2645 30 360 -630 3705 346 333 -637 2553 184 -216 -711 3683 1114 898 -172 5573 2306 729 -115 3231 1306 -273 -672 1503 518 -135 -509 3871 2412 911 275 5151 3566 505 68 3559 2546 115 -2...

result:

ok ok Sum L = 100

Test #6:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

50
-56 747 3
993 -490 4
930 -139 1
-298 -330 1
938 -351 5
-973 100 5
-472 44 4
345 628 5
481 -91 4
789 581 5
457 -29 4
871 -799 1
692 994 4
699 854 2
893 -33 1
-483 256 3
-962 -540 2
846 -893 1
830 609 5
845 -383 2
-552 -966 1
-544 -51 1
564 186 4
-615 -675 1
618 -911 3
-561 -302 4
-293 667 3
-334 -...

output:

5
100 1714 -985 356 -986 4408 -961 348 -975 2592 -921 -552 -966 3132 -793 618 -911 5928 -647 846 -893 5880 -519 594 -847 5930 -331 871 -799 6090 -245 674 -804 6028 77 840 -638 4714 171 17 -757 5020 467 993 -490 6560 985 787 -498 6264 1199 845 -383 6566 1493 938 -351 6736 1981 930 -139 6430 2305 785 ...

result:

ok ok Sum L = 500

Test #7:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

50
600 997 5
-893 -204 3
408 443 1
-560 -748 7
-647 161 6
-285 -980 1
87 -582 7
-48 -721 7
997 285 2
-189 -728 8
525 222 4
-324 816 9
760 317 3
753 -480 10
-813 -921 3
-325 -875 8
-747 816 10
-627 605 7
775 786 6
136 -54 2
274 948 10
216 -113 7
924 68 3
101 576 8
60 -501 2
898 801 8
-767 -974 10
-99...

output:

10
100 359 -995 -313 -996 1753 -961 -285 -980 4243 -851 932 -941 4297 -767 -258 -938 899 -833 -767 -974 1377 -647 -19 -845 2261 -449 -325 -875 2631 -291 166 -766 3819 49 269 -705 4139 293 326 -644 3505 261 -48 -721 4359 589 753 -480 4077 575 -189 -728 2745 371 87 -582 2329 345 -397 -741 529 -333 -81...

result:

ok ok Sum L = 1000

Test #8:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

50
24 -889 49
117 418 49
25 524 44
980 -416 43
-494 357 41
-287 -285 46
151 574 41
-289 68 49
-515 -540 41
-367 -178 47
-887 151 45
197 -272 47
714 724 45
-737 94 49
810 830 47
808 -695 41
537 -637 49
-142 -167 44
-749 -631 47
445 -444 42
801 910 43
59 363 42
-912 466 50
-649 -479 48
-958 -511 49
88...

output:

50
100 1151 -957 75 -958 2583 -873 -282 -917 2481 -735 24 -889 3391 -615 173 -857 3889 -497 273 -830 5159 -173 808 -695 6489 295 938 -596 5947 411 537 -637 6031 771 980 -416 6019 1147 531 -449 4949 1091 445 -444 4165 1089 139 -450 3669 1433 197 -272 5153 2649 881 158 4731 2679 -14 -257 3171 2095 101...

result:

ok ok Sum L = 5000

Test #9:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

50
151 -171 50
-367 -951 50
808 569 50
150 -618 50
27 -476 50
-846 729 50
549 -456 50
50 646 50
294 -70 50
-571 104 50
128 -265 50
913 -700 50
267 -965 50
896 846 50
-2 713 50
21 679 50
-515 975 50
168 180 50
-369 -98 50
676 115 50
643 -779 50
920 -237 50
-324 450 50
149 -378 50
-882 -602 50
-126 -7...

output:

50
100 281 -988 -302 -989 2579 -938 267 -965 4017 -848 417 -944 3877 -764 197 -923 2309 -778 -367 -951 2877 -678 481 -873 4897 -334 643 -779 5761 12 913 -700 6265 442 895 -564 4187 244 -126 -799 3393 100 498 -636 3945 462 150 -618 4047 822 549 -456 4589 1132 421 -463 5381 1544 945 -250 6379 1996 920...

result:

ok ok Sum L = 5000

Test #10:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

50
4 5 34
1 -5 24
-4 -4 32
-3 3 28
0 -1 21
1 -4 25
0 0 30
0 -4 42
-3 -2 44
-5 -3 37
4 -1 46
5 2 20
2 2 37
-2 5 35
-2 -1 39
2 4 32
-4 -3 42
0 3 32
3 5 47
-4 1 2
5 -1 17
-5 -4 5
-2 2 29
-5 1 11
2 -5 43
4 4 14
-5 0 9
0 -5 17
5 1 27
-3 0 24
-1 4 16
5 0 50
3 -2 18
1 -2 6
2 -1 29
-1 3 38
1 5 36
-3 1 28
-3...

output:

50
100 129 60 5 -4 365 186 2 -5 357 184 1 -5 353 184 0 -5 353 186 1 -4 357 190 2 -3 355 190 0 -4 347 186 -2 -5 357 192 5 -1 367 198 3 -2 355 192 -1 -4 357 194 4 -1 359 196 0 -3 361 198 5 0 363 200 1 -2 357 198 2 -1 355 198 0 -2 361 202 5 1 353 198 -4 -4 345 194 1 -1 347 196 -3 -3 335 190 -5 -4 341 1...

result:

ok ok Sum L = 5000

Test #11:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

50
2 0 2
2 -3 2
4 1 2
-3 -3 2
-5 1 2
5 3 2
-5 -3 2
-3 -2 2
2 -1 2
2 3 2
4 4 1
1 -4 1
5 -1 2
-4 1 2
3 -2 1
-1 2 2
5 -5 2
-2 1 2
-5 -1 2
-2 -1 2
-1 -2 2
5 5 1
0 -2 2
1 1 1
2 2 2
3 5 2
-2 -4 1
-3 5 1
4 2 2
-4 -4 2
-3 2 1
5 0 2
-2 -2 2
-4 4 1
-2 5 2
2 5 1
3 -5 2
-4 5 2
-5 5 2
-2 4 2
-5 -5 2
-2 2 2
-3 -4...

output:

2
100 25 55 5 -5 59 183 5 -1 59 193 5 0 55 185 3 -5 55 191 5 3 55 195 3 -3 53 191 4 1 57 207 5 5 55 201 3 -2 53 195 4 2 55 207 4 4 51 195 2 -4 47 181 2 -3 47 185 2 -2 47 189 2 -1 47 193 2 0 45 187 1 -4 47 197 3 5 49 209 2 2 45 195 1 -2 45 197 2 3 47 211 2 5 45 207 1 1 41 193 0 -2 39 189 0 -1 37 185 ...

result:

ok ok Sum L = 200

Test #12:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

50
4 3 49
-5 -3 49
0 -3 50
-2 -4 49
-5 -5 50
4 0 49
-1 -2 49
-2 0 49
1 2 50
-1 -5 50
-5 -1 50
-5 5 49
2 0 50
-2 -3 50
-4 -5 50
0 -2 50
-5 4 50
-1 1 49
-1 -4 49
-3 -1 49
1 -3 50
-4 1 50
0 5 50
1 -2 50
-1 5 50
4 2 50
4 -3 49
1 -4 49
-1 -1 49
-3 -5 50
4 -4 50
3 2 49
3 -3 49
0 2 50
-3 -4 49
5 -1 49
-3 5...

output:

50
100 56 1 2 -5 156 13 1 -5 150 13 -1 -5 142 13 -3 -5 152 15 4 -4 150 15 -4 -5 132 13 -5 -5 142 15 1 -4 152 17 0 -4 148 17 -1 -4 158 19 5 -3 156 19 -2 -4 154 19 4 -3 152 19 -3 -4 150 19 3 -3 158 21 1 -3 152 21 0 -3 146 21 -2 -3 148 23 1 -2 142 23 -5 -3 140 23 0 -2 160 27 5 -1 158 27 -1 -2 154 27 3 ...

result:

ok ok Sum L = 5000

Test #13:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

50
114 514 30
115 514 41
116 514 6
117 514 49
118 514 10
119 514 49
120 514 1
121 514 7
122 514 3
123 514 4
124 514 1
125 514 12
126 514 15
127 514 16
128 514 34
129 514 24
130 514 49
131 514 43
132 514 25
133 514 12
134 514 26
135 514 13
136 514 12
137 514 15
138 514 7
139 514 25
140 514 5
141 514 ...

output:

49
100 329 1029 163 514 653 2059 162 514 649 2059 161 514 645 2059 160 514 641 2059 159 514 637 2059 158 514 633 2059 157 514 629 2059 156 514 625 2059 155 514 621 2059 154 514 617 2059 153 514 613 2059 152 514 609 2059 151 514 605 2059 150 514 601 2059 149 514 597 2059 148 514 593 2059 147 514 589 ...

result:

ok ok Sum L = 4900

Test #14:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

50
191 981 19
191 980 41
191 979 20
191 978 14
191 977 2
191 976 49
191 975 40
191 974 3
191 973 20
191 972 6
191 971 13
191 970 4
191 969 4
191 968 47
191 967 32
191 966 11
191 965 34
191 964 30
191 963 3
191 962 16
191 961 24
191 960 30
191 959 34
191 958 31
191 957 24
191 956 29
191 955 42
191 95...

output:

49
100 385 1865 191 932 767 3733 191 933 767 3737 191 934 767 3741 191 935 767 3745 191 936 767 3749 191 937 767 3753 191 938 767 3757 191 939 767 3761 191 940 767 3765 191 941 767 3769 191 942 767 3773 191 943 767 3777 191 944 767 3781 191 945 767 3785 191 946 767 3789 191 947 767 3793 191 948 767 ...

result:

ok ok Sum L = 4900

Test #15:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

50
-123 456 47
-122 457 35
-121 458 25
-120 459 35
-119 460 30
-118 461 33
-117 462 21
-116 463 31
-115 464 21
-114 465 35
-113 466 20
-112 467 17
-111 468 25
-110 469 3
-109 470 29
-108 471 35
-107 472 4
-106 473 44
-105 474 4
-104 475 28
-103 476 49
-102 477 9
-101 478 39
-100 479 9
-99 480 21
-98...

output:

50
100 -22 1011 -74 505 74 2021 -75 504 70 2017 -76 503 66 2013 -77 502 62 2009 -78 501 58 2005 -79 500 54 2001 -80 499 50 1997 -81 498 46 1993 -82 497 42 1989 -83 496 38 1985 -84 495 34 1981 -85 494 30 1977 -86 493 26 1973 -87 492 22 1969 -88 491 18 1965 -89 490 14 1961 -90 489 10 1957 -91 488 6 19...

result:

ok ok Sum L = 5000

Test #16:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

50
321 -525 46
322 -526 14
323 -527 16
324 -528 38
325 -529 22
326 -530 24
327 -531 48
328 -532 5
329 -533 7
330 -534 30
331 -535 25
332 -536 2
333 -537 13
334 -538 1
335 -539 33
336 -540 8
337 -541 9
338 -542 2
339 -543 29
340 -544 17
341 -545 41
342 -546 39
343 -547 9
344 -548 47
345 -549 47
346 -...

output:

50
100 743 -573 370 -574 1481 -569 369 -573 1477 -565 368 -572 1473 -561 367 -571 1469 -557 366 -570 1465 -553 365 -569 1461 -549 364 -568 1457 -545 363 -567 1453 -541 362 -566 1449 -537 361 -565 1445 -533 360 -564 1441 -529 359 -563 1437 -525 358 -562 1433 -521 357 -561 1429 -517 356 -560 1425 -513...

result:

ok ok Sum L = 5000

Test #17:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

50
-444 -555 23
-445 -556 32
-446 -557 36
-447 -558 29
-448 -559 4
-449 -560 25
-450 -561 29
-451 -562 5
-452 -563 9
-453 -564 28
-454 -565 35
-455 -566 26
-456 -567 22
-457 -568 39
-458 -569 13
-459 -570 50
-460 -571 37
-461 -572 14
-462 -573 26
-463 -574 49
-464 -575 23
-465 -576 44
-466 -577 2
-4...

output:

50
100 -489 -603 -493 -604 -485 -599 -492 -603 -481 -595 -491 -602 -477 -591 -490 -601 -473 -587 -489 -600 -469 -583 -488 -599 -465 -579 -487 -598 -461 -575 -486 -597 -457 -571 -485 -596 -453 -567 -484 -595 -449 -563 -483 -594 -445 -559 -482 -593 -441 -555 -481 -592 -437 -551 -480 -591 -433 -547 -47...

result:

ok ok Sum L = 5000

Test #18:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

50
-142 0 48
-143 1 22
-144 2 45
-145 3 9
-146 4 36
-147 5 46
-148 6 26
-149 7 26
-150 8 9
-151 9 19
-152 10 22
-153 11 14
-154 12 8
-155 13 20
-156 14 41
-157 15 47
-158 16 22
-159 17 50
-160 18 3
-161 19 12
-162 20 15
-163 21 32
-164 22 46
-165 23 45
-166 24 3
-167 25 27
-168 26 33
-169 27 17
-170...

output:

50
100 -90 1 -142 0 6 5 -143 1 2 9 -144 2 -2 13 -145 3 -6 17 -146 4 -10 21 -147 5 -14 25 -148 6 -18 29 -149 7 -22 33 -150 8 -26 37 -151 9 -30 41 -152 10 -34 45 -153 11 -38 49 -154 12 -42 53 -155 13 -46 57 -156 14 -50 61 -157 15 -54 65 -158 16 -58 69 -159 17 -62 73 -160 18 -66 77 -161 19 -70 81 -162 ...

result:

ok ok Sum L = 5000

Test #19:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

12
1000 1000 50
1000 -1000 50
1000 999 50
999 1000 50
999 -1000 50
-999 1000 50
1000 -999 50
-999 -1000 50
-1000 1000 50
-1000 -1000 50
-1000 -999 50
-1000 999 50

output:

50
24 3003 -996 1000 -1000 7001 -988 999 -1000 7001 -986 1000 -999 7003 3012 1000 999 7003 7010 1000 1000 7001 7012 999 1000 3003 3012 -999 -1000 -995 -988 -1000 -1000 -997 -986 -1000 -999 -995 3014 -999 1000 -995 7010 -1000 999 -997 7010 -1000 1000 
24 7007 -988 1000 -1000 15003 -972 999 -1000 1500...

result:

ok ok Sum L = 1200

Test #20:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

4
1000 1000 50
1000 -1000 50
-1000 1000 50
-1000 -1000 50

output:

50
8 3004 -999 1000 -1000 3006 -997 -1000 -1000 3006 3003 1000 1000 3006 7003 -1000 1000 
8 7010 -997 1000 -1000 7014 -993 -1000 -1000 7014 7007 1000 1000 7014 15007 -1000 1000 
8 11016 -995 1000 -1000 11022 -989 -1000 -1000 11022 11011 1000 1000 11022 23011 -1000 1000 
8 15022 -993 1000 -1000 15030...

result:

ok ok Sum L = 400

Extra Test:

score: 0
Extra Test Passed