QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #638457 | #8940. Piggy Sort | ucup-team173# | WA | 0ms | 3892kb | C++20 | 5.5kb | 2024-10-13 15:57:43 | 2024-10-13 15:57:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
bool operator<(pair<ll, ll> a, pair<ll, ll> b) {
return (i128)a.second * b.first < (i128)a.first * b.second;
}
void solve() {
int n, m;
cin >> n >> m;
vector x(m, vector<ll>(n + 1));
vector pos(m, unordered_map<ll, int>());
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
cin >> x[i][j];
pos[i][x[i][j]] = j;
x[i][n] += x[i][j];
}
}
sort(x.begin(), x.end(), [&](vector<ll> &a, vector<ll> &b) {
return a[n] < b[n];
});
ll sv = 0;
for(int i = 1; i < m; i++) {
sv = __gcd(sv, x[i][n] - x[0][n]);
}
if(sv == 0) {
for(int i = 1; i <= n; i++) {
cout << i << " \n"[i == n];
}
return;
}
vector<ll> t(m);
for(int i = 0; i < m; i++) {
t[i] = (x[i][n] - x[0][n]) / sv;
}
vector vis(m, vector(n, 0));
vector<pair<pair<ll, ll>, int>> v(m);
for(int _ = 1; _ < m; _++) {
int flg = 1;
vector beg(m, 0);
{
pair<ll, ll> vel;
ll x0 = -1e9;
vel = {t[_] - t[_ - 1], x[_][0] - x[_ - 1][0]};
auto [dx, dy] = vel;
if(dy * t[_] % dx) continue;
x0 = x[_][0] - dy * t[_] / dx;
vis.assign(m, vector(n, 0));
for(int i = 0; i < m && flg; i++) {
ll yi = x0 + dy * t[i] / dx;
if(pos[i].find(yi) == pos[i].end()) {
flg = 0;
} else {
vis[i][pos[i][yi]] = 1;
}
}
int id = pos[0][x0];
v[id] = {vel, id};
}
for(int __ = 1; __ < n && flg; __++) {
vector y(m, ll(1e9));
for(int i = 0; i < m; i++) {
while(vis[i][beg[i]]) beg[i]++;
y[i] = x[i][beg[i]];
}
ll x0 = -1e9;
pair<ll, ll> vel;
auto chk = [&](pair<ll, ll> a, pair<ll, ll> b) {
return a.second * b.first == a.first * b.second;
};
for(int i = 1; i < m; i++) {
pair<ll, ll> l = {t[i] - t[i - 1], y[i] - y[i - 1]};
pair<ll, ll> r;
if(i + 1 < m) r = {t[i + 1] - t[i], y[i + 1] - y[i]};
if(i == m - 1 || chk(l, r)) {
auto [dx, dy] = l;
vel = l;
x0 = y[i] - dy * t[i] / dx;
break;
}
}
if(pos[0].find(x0) == pos[0].end()) {
flg = 0;
break;
}
int id = pos[0][x0];
auto [dx, dy] = vel;
v[id] = {vel, id};
for(int i = 0; i < m; i++) {
ll y = x0 + dy * t[i] / dx;
if(pos[i].find(y) == pos[i].end()) {
flg = 0;
} else {
vis[i][pos[i][y]] = 1;
}
}
}
if(flg) break;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j + 1 < n; j++) {
if(v[j + 1].first < v[j].first) {
swap(v[j], v[j + 1]);
}
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[v[i].second] = i;
for(int i = 0; i < n; i++) {
cout << ans[i] + 1 << " \n"[i == n - 1];
}
// for(int _ = 0; _ < n; _++) {
// vector y(m, ll(1e9));
// for(int i = 0; i < m; i++) {
// for(int j = 0; j < n; j++) {
// if(!vis[i][j]) y[i] = min(y[i], x[i][j]);
// }
// }
// ll x0 = -1e9;
// pair<ll, ll> vel;
// if(_ == 0) {
// for(int i = 1; i < m; i++) {
// vel = {t[i] - t[i - 1], y[i] - y[i - 1]};
// auto [dx, dy] = vel;
// if(dy * t[i] % dx) continue;
// x0 = y[i] - dy * t[i] / dx;
// int flg = 1;
// for(int j = 0; j < m && flg; j++) {
// ll yj = x0 + dy * t[j] / dx;
// flg &= pos[j].find(yj) != pos[j].end();
// }
// if(flg) break;
// }
// } else {
// auto chk = [&](pair<ll, ll> a, pair<ll, ll> b) {
// return a.second * b.first == a.first * b.second;
// };
// for(int i = 1; i < m; i++) {
// pair<ll, ll> l = {t[i] - t[i - 1], y[i] - y[i - 1]};
// pair<ll, ll> r;
// if(i + 1 < m) r = {t[i + 1] - t[i], y[i + 1] - y[i]};
// if(i == m - 1 || chk(l, r)) {
// auto [dx, dy] = l;
// vel = l;
// x0 = y[i] - dy * t[i] / dx;
// break;
// }
// }
// }
// int id = -1;
// for(int i = 0; i < n; i++) if(x[0][i] == x0) id = i;
// auto [dx, dy] = vel;
// v[id] = {vel, id};
// for(int i = 0; i < m; i++) {
// ll y = x0 + dy * t[i] / dx;
// assert(pos[i].find(y) != pos[i].end());
// vis[i][pos[i][y]] = 1;
// }
// }
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
/*
1
2 3
1 11
11 12
13 21
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
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: -100
Wrong Answer
time: 0ms
memory: 3892kb
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 2 1 10 2 1 1 1 1 1 1 1 1 9 1 1 1 6 5 1 1 1 10 1 3 1 1 6 1 1 1 1 9 1 1 1 1 1 1 1 1 10 8 1 3 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 4 1 3 1 9 1 1 4 1 1 1 1 1 9 1 1 1 1 1 1 1 1 8 1 1 1 5 1 1 1 9 10 2 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 9 1 3 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 10 3 1 1 1 1 1 ...
result:
wrong answer 2nd lines differ - expected: '1 2', found: '2 1'