Submission #751545

#	Time	Username	Problem	Language	Result	Execution time	Memory
751545		stevancv	Project of Migration (JOI14_migration)	Text	0 / 100	0 ms	0 KiB

01-out

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e3 + 2;
const int inf = 2e9;
int ori(array<ll, 2> a, array<ll, 2> b, array<ll, 2> c) {
    ll o = (b[0] - a[0]) * (c[1] - b[1]) - (c[0] - b[0]) * (b[1] - a[1]);
    if (o > 0) return 1;
    else return 0;
}
bool intersect(array<ll, 2> a, array<ll, 2> b, array<ll, 2> c, array<ll, 2> d) {
    return ((ori(a,b,c)==ori(a,b,d)) && (ori(c,d,a)==ori(c,d,b)));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<array<int, 2>> e(m);
    for (int i = 0; i < m; i++) {
        cin >> e[i][0] >> e[i][1];
        e[i][0] -= 1; e[i][1] -= 1;
    }
    int k; cin >> k;
    vector<array<ll, 2>> p(k);
    for (int i = 0; i < k; i++) {
        cin >> p[i][0] >> p[i][1];
    }
    ll mn = 1e18;
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    mt19937 mt(time(nullptr));
    int P = 1000;
    while (P--) {
        vector<int> is(k);
        vector<int> cur(n);
        for (int i = 0; i < n; i++) {
            int cnt = (mt() % (k - accumulate(is.begin(), is.end(), 0))) + 1;
            for (int j = 0; j < k; j++) {
                if (!is[j]) cnt--;
                if (cnt == 0) {
                    cur[i] = j;
                    is[j] = 1;
                    break;
                }
            }
        }
        auto F = [&] (vector<int> f) {
            ll cu = 0;
            for (int I = 0; I < m; I++) {
                for (int J = I + 1; J < m; J++) {
                    if (e[I][0] == e[J][0] || e[I][0] == e[J][1]
                        || e[I][1] == e[J][0] || e[I][1] == e[J][1]) continue;
                    if (intersect(p[f[e[I][0]]], p[f[e[I][1]]], p[f[e[J][0]]], p[f[e[J][1]]])) cu++;
                }
            }
            return cu;
        };
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(cur[i], cur[j]);
                ll x = F(cur);
                if (x < mn) {
                    mn = x;
                    ans = cur;
                }
                else swap(cur[i], cur[j]);
            }
        }
    }
    cout << mn << en;
    for (int i = 0; i < n; i++) cout << ans[i] + 1 << en;
    return 0;
}
/*
30 50
8 16
19 22
20 27
22 25
2 23
10 11
2 20
10 18
10 28
15 25
2 16
19 25
8 11
1 22
18 27
29 30
13 30
9 18
20 28
14 30
27 29
4 12
5 22
3 22
4 21
16 28
21 27
20 22
26 28
25 27
12 25
18 23
15 17
16 20
6 10
4 10
24 30
3 30
7 19
23 26
1 18
11 20
23 25
28 29
5 20
8 30
17 30
9 24
2 17
1 3
60
24193 67416
60315 81699
30623 75952
35762 79997
62066 19951
22490 15142
50470 57850
39885 82743
74504 87339
29019 98565
52160 35475
31674 88458
81564 82146
65135 26406
61062 36262
32397 34797
31934 94348
53586 80373
70174 28719
8956 59596
2884 73135
45150 70926
52194 96187
47338 74028
89530 14085
33656 67992
40895 38196
82002 73612
63849 17504
53672 48819
20718 89820
13247 88089
26154 29353
29979 77381
24653 38986
32431 72724
19737 25277
53274 55205
74298 16536
73295 22475
4618 2613
62229 79643
78491 50291
17456 89413
98336 87345
36401 25492
13278 69423
38174 23794
49970 36494
44404 8374
86056 71291
14653 24242
98375 48971
1473 24884
45029 8410
85238 53754
81670 36356
60388 3013
89981 10613
75730 62475

*/

02-out

03-out

04-out

05-out

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20