QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#610779#8940. Piggy SortUESTC_NLNSRE 1ms3652kbC++202.7kb2024-10-04 17:22:242024-10-04 17:22:26

Judging History

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

  • [2024-10-04 17:22:26]
  • 评测
  • 测评结果：RE
  • 用时：1ms
  • 内存：3652kb
查看
  • [2024-10-04 17:22:24]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
using ll = long long;
using ldb = long double;
const ll inf = 1LL * 0x3f3f3f3f * 0x3f3f3f3f;
struct point {
    ll x, y;
};

struct item {
    ll v, x, id;
};

using i128 = __int128_t;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(m, vector<int>(n));
    vector<item> val(n);
    vector<ll> t(m);

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) cin >> a[i][j], t[i] += a[i][j];

    for (int i = 0; i < n; ++i) {
        val[i].x = a[0][i];
        val[i].id = i;
    }
    vector<unordered_map<ll, int>> mp(m);

    auto add = [&](int i, ll v) {
        if (mp[i].find(v) == mp[i].end())
            mp[i][v] = 1;
        else
            mp[i][v]++;
    };

    auto sub = [&](int i, ll v) { mp[i][v]--; };

    auto in = [&](int i, ll v) { return mp[i].find(v) != mp[i].end() && mp[i][v] > 0; };

    auto get = [&](const point& a1, const point& a2, ll t) -> ll {
        i128 p = i128(a1.x - a2.x) * (t - a1.y);
        ll q = (a1.y - a2.y);
        if (p % q != 0 || p / q > inf) return inf;
        return a1.x + p / q;
    };

    for (int k = 2; k < m; ++k) {
        for (const int u : a[k]) {
            add(k, u);
        }
    }
    vector<int> vis(n);
    for (int i = 0; i < n; ++i) {
        point p1 = {a[0][i], t[0]};
        for (int j = 0; j < n; ++j) {
            if (vis[j]) continue;
            point p2 = {a[1][j], t[1]};
            int ok = 1;
            for (int k = 2; k < m; ++k) {
                ll tmp = get(p1, p2, t[k]);
                if (!in(k, tmp)) {
                    ok = 0;
                    break;
                }
            }
            if (!ok) continue;
            for (int k = 2; k < m; ++k) {
                ll tmp = get(p1, p2, t[k]);
                sub(k, tmp);
                val[i].v = a[1][j] - a[0][i];
                vis[j] = 1;
            }
            break;
        }
    }
    sort(val.begin(), val.end(), [](const item& a, const item& b) {
        if (a.v != b.v) return a.v < b.v;
        return a.x < b.x;
    });
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[val[i].id] = i;
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] + 1 << " ";
    }

    cout << '\n';
}

int main() {

    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) solve();
}
/*
3
5 7
-5 -1 7 8 10
-1 1 10 19 20
-1 4 10 25 26
-1 5 10 27 28
-2 -1 10 13 14
-4 -1 9 10 10
-1 3 10 23 24
5 6
-7 -5 2 3 5
2 3 11 13 14
-5 -3 2 3 6
2 3 7 9 12
2 3 3 5 10
2 3 5 7 11
3 4
-10 -7 -5
-10 1 3
-10 -4 -2
-10 0 2
*/
源文件, 语言: C++20

詳細信息

Test #1:

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

input:

3
2 4
1 2
3 4
5 6
7 8
1 2
1
1
3 4
1 2 3
6 9 9
10 15 17
12 18 21

output:

1 2 
1 
3 1 2

result:

ok 3 lines

Test #2:

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

input:

41
1 2
-19
9531
2 3
11 13
3175 4759
2211 3313
10 19
-54 -25 -19 -18 -1 3 61 63 85 88
-54 753 863 2397 3111 4649 4671 4756 5507 7762
-54 369 479 1245 1575 2345 2367 2452 2819 3922
-54 553 663 1797 2311 3449 3471 3556 4107 5762
-54 87 197 399 447 653 675 760 845 1102
-54 320 430 1098 1379 2051 2073 21...

output:

1 
1 2 
1 2 6 10 5 7 9 4 3 8 
8 7 5 9 2 1 6 3 4 
1 6 5 9 8 2 3 10 4 7 
3 5 10 6 7 4 9 8 2 1 
4 3 1 8 2 5 6 7 
3 1 5 2 6 9 8 7 4 10 
2 3 1 4 
3 2 9 1 4 6 7 5 8 
1 5 2 6 7 3 4 8 9 
9 8 5 7 2 3 4 6 1 
1 2 4 8 5 7 10 6 9 3 
7 1 3 2 9 8 10 4 5 6 
7 8 1 2 5 6 3 9 4 
8 1 2 7 6 9 3 5 4 
8 1 2 4 5 10 9 3 6 7...

result:

ok 41 lines

Test #3:

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

input:

46
8 12
-50 -35 -20 -10 -9 4 13 91
-24 30 32 143 146 147 173 221
-44 -8 10 13 26 27 61 103
-46 -12 -3 8 14 15 45 99
-22 32 36 147 158 159 189 237
-47 -14 -11 7 8 9 37 97
-31 18 23 104 105 117 129 165
-45 -10 5 9 20 21 53 101
-36 8 18 74 75 77 119 125
-30 20 24 110 111 125 131 173
-48 -19 -16 2 3 6 2...

output:

1 7 3 5 6 2 8 4 
1 2 3 
3 6 1 5 10 8 7 2 9 4 
2 5 3 6 9 10 8 7 1 4 
1 4 5 2 6 3 7 
8 6 4 5 7 9 2 3 1 
6 7 2 8 9 1 10 3 5 4 
4 5 1 3 2 
1 2 
1 2 4 5 7 6 3 8 9 
6 3 4 9 7 1 2 8 10 5 
1 6 7 8 4 9 5 3 2 
1 4 2 6 5 8 3 7 
2 1 
5 1 7 6 3 2 4 
7 3 8 4 1 2 9 5 6 10 
6 1 2 5 3 4 
2 1 3 4 
7 8 5 9 2 1 4 3 6 
...

result:

ok 46 lines

Test #4:

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

input:

48
3 4
-4952 -1539 836
-4294 5909 12778
-4811 57 3395
-4529 3249 8513
8 11
-9107 -1143 1324 3936 4088 4381 7658 9440
-2753 531 6032 14986 18097 18264 20240 22022
-5224 -120 5276 9673 12692 12763 15347 17129
-2047 717 6248 16504 19621 19856 21638 23420
-6283 -399 4952 7396 10304 10477 13250 15032
-48...

output:

1 2 3 
3 1 6 8 2 7 4 5 
8 4 6 1 2 9 10 5 3 7 
1 2 3 
6 1 10 7 5 3 9 4 8 2 
1 2 
8 3 2 7 10 6 1 9 5 4 
9 5 2 7 6 1 8 4 3 
6 4 3 2 7 5 1 
1 4 2 3 
1 
3 8 9 6 7 4 1 2 10 5 
5 1 6 4 2 3 
2 1 9 6 4 5 3 8 7 
3 5 6 7 9 2 4 8 1 
4 2 1 3 5 6 
4 5 6 3 7 1 2 
1 
9 7 10 1 8 5 3 6 2 4 
8 3 6 9 2 5 4 7 1 
4 3 9 5...

result:

ok 48 lines

Test #5:

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

input:

40
10 20
-4289879 -3663596 -3442064 -3379220 -670906 -329052 1547135 1640345 2662172 3577480
-4280827 -3609576 -3374758 -3321039 -598417 -319197 1583489 1685532 2700424 3645662
-4276115 -3581456 -3339722 -3290753 -560683 -314067 1602413 1709054 2720336 3681154
-4271279 -3552596 -3303764 -3259670 -52...

output:

1 6 8 7 10 2 3 5 4 9 
2 3 1 
9 8 3 6 4 2 10 1 7 5 
2 1 8 5 3 4 10 7 6 9 
7 2 6 1 9 5 8 3 4 
2 6 3 9 7 1 4 5 8 
3 6 7 5 1 2 8 4 
3 4 10 9 8 7 6 2 5 1 
3 8 2 6 1 4 5 7 
4 2 5 7 1 6 3 
1 8 3 10 9 7 4 6 5 2 
1 3 5 4 2 
8 6 7 3 1 4 5 10 2 9 
1 2 3 
5 10 2 7 6 4 1 8 3 9 
4 10 7 6 8 9 5 1 2 3 
5 7 10 1 4 9...

result:

ok 40 lines

Test #6:

score: -100
Runtime Error

input:

79
5 7
-5 -1 7 8 10
-1 1 10 19 20
-1 4 10 25 26
-1 5 10 27 28
-2 -1 10 13 14
-4 -1 9 10 10
-1 3 10 23 24
5 6
-7 -5 2 3 5
2 3 11 13 14
-5 -3 2 3 6
2 3 7 9 12
2 3 3 5 10
2 3 5 7 11
3 4
-10 -7 -5
-10 1 3
-10 -4 -2
-10 0 2
5 10
-10 -6 -1 6 7
-10 4 7 9 11
-10 7 8 13 13
-10 7 14 16 19
-10 7 12 15 17
-10 6...

output:

result:
English 繁體中文 简体中文

伺服器時間: 2025-02-02 04:51:29 | 開源專案