#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
struct Frac {
int x, y;
Frac(int _x = 0, int _y = 1) {
x = _x; y = _y;
simp();
}
void simp() {
int g = __gcd(x, y);
x /= g; y /= g;
}
};
Frac operator-(const Frac &a) {
return Frac(-a.x, a.y);
}
Frac operator+(const Frac &a, const Frac &b) {
return Frac(a.x * b.y + a.y * b.x, a.y * b.y);
}
Frac operator-(const Frac &a, const Frac &b) {
return a + (-b);
}
Frac operator*(const Frac &a, const Frac &b) {
return Frac(a.x * b.x, a.y * b.y);
}
Frac operator/(const Frac &a, const Frac &b) {
return Frac(a.x * b.y, a.y * b.x);
}
bool operator==(const Frac &a, const Frac &b) {
return a.x * b.y == a.y * b.x;
}
bool operator<(const Frac &a, const Frac &b) {
return a.x * b.y < a.y * b.x;
}
bool operator>(const Frac &a, const Frac &b) {
return b < a;
}
bool operator<=(const Frac &a, const Frac &b) {
return a < b || a == b;
}
bool operator>=(const Frac &a, const Frac &b) {
return a > b || a == b;
}
ostream& operator<<(ostream& os, const Frac &a) {
os << a.x << "/" << a.y;
return os;
}
const int MAXN = 2010;
struct Meow {
int v[MAXN];
Frac tar;
Frac inq[MAXN];
Frac rem[MAXN];
int pos_r, pos_l;
Frac now;
bool used;
void init(int n, int l) {
used = false;
tar = Frac();
For(i, 1, l) {
cin >> v[i];
tar.x += v[i];
rem[i] = Frac(1);
}
tar = tar / n;
pos_r = 1; pos_l = 1;
now = Frac(0);
push(1, Frac(0));
}
void push(int p0, Frac par) {
while(pos_l < p0) {
now = now - inq[pos_l] * v[pos_l];
pos_l++;
}
// cout << rem[pos_r] << " " << tar << " " << now << "\n" << flush;
Frac t = inq[pos_l] + rem[pos_r] + par - 1;
inq[pos_l] = inq[pos_l] - t;
now = now - t * v[pos_l];
while(now + rem[pos_r] * v[pos_r] < tar) {
now = now + rem[pos_r] * v[pos_r];
inq[pos_r] = inq[pos_r] + rem[pos_r];
rem[pos_r] = 0;
pos_r++;
}
t = (tar - now) / v[pos_r];
assert(t <= rem[pos_r]);
rem[pos_r] = rem[pos_r] - t;
inq[pos_r] = inq[pos_r] + t;
now = tar;
}
pair<int, Frac> get_front() {
return make_pair(pos_r, 1 - rem[pos_r]);
}
} meow[MAXN];
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// nyanyanyanyanya
int n, l; cin >> n >> l;
// assert(n <= 6);
For(i, 1, n) meow[i].init(n, l);
vector<int> ans;
For(i, 1, n - 1) {
pair<int, Frac> front(l + 1, 0);
int min_id = -1;
For(j, 1, n) if(!meow[j].used) {
if(meow[j].get_front() < front) {
front = meow[j].get_front();
min_id = j;
}
auto p = meow[j].get_front();
// cout << j << " : " << p.F << " - " << p.S << "\n" << flush;
}
assert(min_id > 0);
ans.eb(min_id);
meow[min_id].used = true;
For(j, 1, n) if(!meow[j].used) {
meow[j].push(front.F, front.S);
}
front.S = front.F - 1 + front.S;
cout << front.S.x << " " << front.S.y << "\n";
}
for(auto &i:ans) cout << i << " ";
For(i, 1, n) if(!meow[i].used) cout << i << "\n";
return 0;
}
Compilation message
naan.cpp: In function 'int32_t main()':
naan.cpp:126:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
126 | auto p = meow[j].get_front();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
134904 KB |
Output is correct |
2 |
Correct |
58 ms |
135000 KB |
Output is correct |
3 |
Correct |
52 ms |
134900 KB |
Output is correct |
4 |
Correct |
55 ms |
134908 KB |
Output is correct |
5 |
Correct |
50 ms |
134916 KB |
Output is correct |
6 |
Correct |
51 ms |
134988 KB |
Output is correct |
7 |
Correct |
51 ms |
134936 KB |
Output is correct |
8 |
Correct |
51 ms |
134964 KB |
Output is correct |
9 |
Correct |
58 ms |
135048 KB |
Output is correct |
10 |
Correct |
55 ms |
135012 KB |
Output is correct |
11 |
Correct |
51 ms |
135000 KB |
Output is correct |
12 |
Correct |
52 ms |
135116 KB |
Output is correct |
13 |
Correct |
52 ms |
134928 KB |
Output is correct |
14 |
Correct |
54 ms |
134924 KB |
Output is correct |
15 |
Correct |
52 ms |
134924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
134888 KB |
Output is correct |
2 |
Correct |
51 ms |
134988 KB |
Output is correct |
3 |
Correct |
52 ms |
134988 KB |
Output is correct |
4 |
Correct |
53 ms |
135068 KB |
Output is correct |
5 |
Correct |
53 ms |
135072 KB |
Output is correct |
6 |
Correct |
56 ms |
134988 KB |
Output is correct |
7 |
Correct |
53 ms |
134988 KB |
Output is correct |
8 |
Correct |
56 ms |
134900 KB |
Output is correct |
9 |
Correct |
53 ms |
135044 KB |
Output is correct |
10 |
Correct |
53 ms |
135116 KB |
Output is correct |
11 |
Correct |
54 ms |
134988 KB |
Output is correct |
12 |
Correct |
59 ms |
134880 KB |
Output is correct |
13 |
Correct |
53 ms |
134972 KB |
Output is correct |
14 |
Correct |
61 ms |
135060 KB |
Output is correct |
15 |
Correct |
54 ms |
134984 KB |
Output is correct |
16 |
Correct |
57 ms |
135056 KB |
Output is correct |
17 |
Correct |
60 ms |
134984 KB |
Output is correct |
18 |
Correct |
53 ms |
134988 KB |
Output is correct |
19 |
Correct |
62 ms |
135044 KB |
Output is correct |
20 |
Correct |
55 ms |
135036 KB |
Output is correct |
21 |
Correct |
54 ms |
134980 KB |
Output is correct |
22 |
Correct |
52 ms |
134984 KB |
Output is correct |
23 |
Correct |
54 ms |
134904 KB |
Output is correct |
24 |
Correct |
55 ms |
134988 KB |
Output is correct |
25 |
Correct |
53 ms |
134976 KB |
Output is correct |
26 |
Correct |
59 ms |
134920 KB |
Output is correct |
27 |
Correct |
54 ms |
134980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
134904 KB |
Output is correct |
2 |
Correct |
58 ms |
135000 KB |
Output is correct |
3 |
Correct |
52 ms |
134900 KB |
Output is correct |
4 |
Correct |
55 ms |
134908 KB |
Output is correct |
5 |
Correct |
50 ms |
134916 KB |
Output is correct |
6 |
Correct |
51 ms |
134988 KB |
Output is correct |
7 |
Correct |
51 ms |
134936 KB |
Output is correct |
8 |
Correct |
51 ms |
134964 KB |
Output is correct |
9 |
Correct |
58 ms |
135048 KB |
Output is correct |
10 |
Correct |
55 ms |
135012 KB |
Output is correct |
11 |
Correct |
51 ms |
135000 KB |
Output is correct |
12 |
Correct |
52 ms |
135116 KB |
Output is correct |
13 |
Correct |
52 ms |
134928 KB |
Output is correct |
14 |
Correct |
54 ms |
134924 KB |
Output is correct |
15 |
Correct |
52 ms |
134924 KB |
Output is correct |
16 |
Correct |
54 ms |
134888 KB |
Output is correct |
17 |
Correct |
51 ms |
134988 KB |
Output is correct |
18 |
Correct |
52 ms |
134988 KB |
Output is correct |
19 |
Correct |
53 ms |
135068 KB |
Output is correct |
20 |
Correct |
53 ms |
135072 KB |
Output is correct |
21 |
Correct |
56 ms |
134988 KB |
Output is correct |
22 |
Correct |
53 ms |
134988 KB |
Output is correct |
23 |
Correct |
56 ms |
134900 KB |
Output is correct |
24 |
Correct |
53 ms |
135044 KB |
Output is correct |
25 |
Correct |
53 ms |
135116 KB |
Output is correct |
26 |
Correct |
54 ms |
134988 KB |
Output is correct |
27 |
Correct |
59 ms |
134880 KB |
Output is correct |
28 |
Correct |
53 ms |
134972 KB |
Output is correct |
29 |
Correct |
61 ms |
135060 KB |
Output is correct |
30 |
Correct |
54 ms |
134984 KB |
Output is correct |
31 |
Correct |
57 ms |
135056 KB |
Output is correct |
32 |
Correct |
60 ms |
134984 KB |
Output is correct |
33 |
Correct |
53 ms |
134988 KB |
Output is correct |
34 |
Correct |
62 ms |
135044 KB |
Output is correct |
35 |
Correct |
55 ms |
135036 KB |
Output is correct |
36 |
Correct |
54 ms |
134980 KB |
Output is correct |
37 |
Correct |
52 ms |
134984 KB |
Output is correct |
38 |
Correct |
54 ms |
134904 KB |
Output is correct |
39 |
Correct |
55 ms |
134988 KB |
Output is correct |
40 |
Correct |
53 ms |
134976 KB |
Output is correct |
41 |
Correct |
59 ms |
134920 KB |
Output is correct |
42 |
Correct |
54 ms |
134980 KB |
Output is correct |
43 |
Runtime error |
214 ms |
262144 KB |
Execution killed with signal 6 |
44 |
Halted |
0 ms |
0 KB |
- |