#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const double PI=acos(-1);
const ll maxn = 4e5+5;
const ll maxm = 3e3+5;
const ll inf = 1ll<<60;
const ll mod = 998244353;
ll pw(ll a, ll p){
ll ret = 1;
while(p > 0){
if (p&1){
ret *= a;
ret %= mod;
}
a *= a;
a %= mod;
p >>= 1;
}
return ret;
}
ll inv(ll a){
return pw(a, mod-2);
}
int n, L;
struct frac{
int num, dem;
};
frac simp(frac &a){
if (a.num == 0) return a;
int g = __gcd(a.num, a.dem);
return {a.num/g, a.dem/g};
}
frac operator +(frac &a, frac &b){
frac tmp = {a.num*b.dem + a.dem*b.num, a.dem*b.dem};
return simp(tmp);
}
frac operator -(frac &a, frac &b){
frac tmp = {a.num*b.dem - a.dem*b.num, a.dem*b.dem};
return simp(tmp);
}
frac operator *(frac &a, frac &b){
frac tmp = {a.num*b.num, a.dem*b.dem};
return simp(tmp);
}
bool operator <(frac &a, frac &b){
return (__int128)a.num*b.dem < (__int128)a.dem*b.num;
}
signed main(){
IOS();
cin>>n>>L;
vector<vector<frac>> vc(n);
vector<vector<int>> in(n);
vector<vector<frac>> pls(n);
REP(i, n){
vc[i].resize(L);
in[i].resize(L);
pls[i].resize(n);
int tot = 0;
REP(j, L) {
cin>>vc[i][j].num;
in[i][j] = vc[i][j].num;
tot += vc[i][j].num;
vc[i][j].dem = 1;
}
int tt = 0;
REP(j, n){
frac gl = {tot, n};
while(vc[i][tt] < gl){
gl = (gl-vc[i][tt]);
vc[i][tt] = {0, 1};
tt++;
}
//cout<<gl.num<<"///"<<gl.dem<<endl;
//cout<<vc[i][tt].num<<"///"<<vc[i][tt].dem<<' '<<tt<<endl;
frac tmp = {tt+1, 1};
vc[i][tt] = (vc[i][tt] - gl);
frac tmp2 = {vc[i][tt].num, vc[i][tt].dem*in[i][tt]};
pls[i][j] = (tmp - tmp2);
//cout<<pls[i][j].num<<'/'<<pls[i][j].dem<<' ';
if (vc[i][tt].num == 0){ // 0
//cout<<tt<<endl;
tt++;
}
}
}
vector<int> perm;
vector<bool> occ(n);
REP(i, n){
pair<frac, int> mn = {{L+1, 1}, -1};
REP(j, n){
if (!occ[j] && pls[j][i] < mn.f) {
mn.f = pls[j][i];
mn.s = j;
}
}
if (i != n-1) cout<<mn.f.num<<' '<<mn.f.dem<<endl;
perm.pb(mn.s+1);
occ[mn.s] = 1;
}
REP(i, n) cout<<perm[i]<<' ';
cout<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
600 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
604 KB |
Output is correct |
34 |
Correct |
1 ms |
604 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
1 ms |
604 KB |
Output is correct |
37 |
Correct |
1 ms |
604 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
604 KB |
Output is correct |
40 |
Correct |
1 ms |
604 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
604 KB |
Output is correct |
43 |
Correct |
62 ms |
11600 KB |
Output is correct |
44 |
Correct |
399 ms |
69968 KB |
Output is correct |
45 |
Correct |
156 ms |
38200 KB |
Output is correct |
46 |
Correct |
16 ms |
5208 KB |
Output is correct |
47 |
Correct |
244 ms |
48620 KB |
Output is correct |
48 |
Correct |
494 ms |
75600 KB |
Output is correct |
49 |
Correct |
114 ms |
23992 KB |
Output is correct |
50 |
Correct |
660 ms |
121208 KB |
Output is correct |
51 |
Correct |
253 ms |
57912 KB |
Output is correct |
52 |
Correct |
573 ms |
122960 KB |
Output is correct |
53 |
Correct |
512 ms |
98120 KB |
Output is correct |
54 |
Correct |
1 ms |
604 KB |
Output is correct |
55 |
Correct |
227 ms |
34928 KB |
Output is correct |
56 |
Correct |
344 ms |
78160 KB |
Output is correct |
57 |
Correct |
276 ms |
62900 KB |
Output is correct |
58 |
Correct |
462 ms |
92244 KB |
Output is correct |
59 |
Correct |
293 ms |
69972 KB |
Output is correct |
60 |
Correct |
659 ms |
156756 KB |
Output is correct |
61 |
Correct |
725 ms |
156872 KB |
Output is correct |
62 |
Correct |
809 ms |
156152 KB |
Output is correct |
63 |
Correct |
775 ms |
157104 KB |
Output is correct |
64 |
Correct |
692 ms |
157264 KB |
Output is correct |
65 |
Correct |
762 ms |
157008 KB |
Output is correct |
66 |
Correct |
730 ms |
157248 KB |
Output is correct |
67 |
Correct |
652 ms |
157132 KB |
Output is correct |
68 |
Correct |
306 ms |
68968 KB |
Output is correct |
69 |
Correct |
306 ms |
75252 KB |
Output is correct |
70 |
Correct |
379 ms |
81236 KB |
Output is correct |
71 |
Correct |
473 ms |
111956 KB |
Output is correct |