| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 111908 |
2019-05-16T17:32:02 Z |
model_code |
Naan (JOI19_naan) |
C++17 |
|
2325 ms |
131736 KB |
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long Int;
typedef pair<Int, Int> P;
typedef pair<Int, P> T;
bool used[2222];
Int v[2222][2222];
Int a[2222];
Int sum[2222];
vector<T> ans;
vector<T> split[2222];
//compare two mixed fractions.
//returns a < b
bool small(T a, T b){
if(a.first < b.first)return true;
if(a.first > b.first)return false;
return a.second.first * b.second.second < a.second.second * b.second.first;
}
//greatest common divisor
Int gcd(Int a, Int b){
if(a == 0)return b;
return gcd(b % a, a);
}
//c + a / b
T make_frac(Int c, Int a, Int b){
Int g = gcd(a , b);
return T(c, P(a / g, b / g));
}
int main(){
Int n, l;
cin >> n >> l;
for(int i = 0;i < n;i++){
for(int j = 0;j < l;j++){
cin >> v[i][j];
sum[i] += v[i][j];
}
}
for(int i = 0;i < n;i++){
Int acum = 0;
Int p = 0;
for(int j = 1;j <= n-1;j++){
while((acum + v[i][p]) * n <= sum[i] * j)acum += v[i][p++];
Int rest = sum[i]*j - acum*n;
split[i].push_back(make_frac(p, rest, n * v[i][p]));
}
split[i].push_back(T(l, P(0, 1)));
}
for(int i = 0;i < n;i++){
Int nxt = -1;
for(int j = 0;j < n;j++){
if(used[j])continue;
if(nxt == -1 || small(split[j][i], split[nxt][i]))nxt = j;
}
used[nxt] = true;
a[i] = nxt;
ans.push_back(split[nxt][i]);
}
for(int i = 0;i < n-1;i++){
cout << ans[i].first*ans[i].second.second + ans[i].second.first << " " << ans[i].second.second << endl;
}
for(int i = 0;i < n;i++){
if(i)cout << " ";
cout << a[i]+1;
}cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
3 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Correct |
4 ms |
512 KB |
Output is correct |
| 12 |
Correct |
3 ms |
380 KB |
Output is correct |
| 13 |
Correct |
3 ms |
512 KB |
Output is correct |
| 14 |
Correct |
5 ms |
512 KB |
Output is correct |
| 15 |
Correct |
4 ms |
512 KB |
Output is correct |
| 16 |
Correct |
4 ms |
512 KB |
Output is correct |
| 17 |
Correct |
5 ms |
512 KB |
Output is correct |
| 18 |
Correct |
5 ms |
512 KB |
Output is correct |
| 19 |
Correct |
7 ms |
512 KB |
Output is correct |
| 20 |
Correct |
5 ms |
512 KB |
Output is correct |
| 21 |
Correct |
5 ms |
512 KB |
Output is correct |
| 22 |
Correct |
4 ms |
512 KB |
Output is correct |
| 23 |
Correct |
2 ms |
384 KB |
Output is correct |
| 24 |
Correct |
4 ms |
512 KB |
Output is correct |
| 25 |
Correct |
4 ms |
512 KB |
Output is correct |
| 26 |
Correct |
3 ms |
384 KB |
Output is correct |
| 27 |
Correct |
4 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Correct |
3 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
3 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
512 KB |
Output is correct |
| 18 |
Correct |
3 ms |
512 KB |
Output is correct |
| 19 |
Correct |
5 ms |
512 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Correct |
4 ms |
384 KB |
Output is correct |
| 22 |
Correct |
3 ms |
384 KB |
Output is correct |
| 23 |
Correct |
3 ms |
512 KB |
Output is correct |
| 24 |
Correct |
3 ms |
512 KB |
Output is correct |
| 25 |
Correct |
5 ms |
512 KB |
Output is correct |
| 26 |
Correct |
4 ms |
512 KB |
Output is correct |
| 27 |
Correct |
3 ms |
380 KB |
Output is correct |
| 28 |
Correct |
3 ms |
512 KB |
Output is correct |
| 29 |
Correct |
5 ms |
512 KB |
Output is correct |
| 30 |
Correct |
4 ms |
512 KB |
Output is correct |
| 31 |
Correct |
4 ms |
512 KB |
Output is correct |
| 32 |
Correct |
5 ms |
512 KB |
Output is correct |
| 33 |
Correct |
5 ms |
512 KB |
Output is correct |
| 34 |
Correct |
7 ms |
512 KB |
Output is correct |
| 35 |
Correct |
5 ms |
512 KB |
Output is correct |
| 36 |
Correct |
5 ms |
512 KB |
Output is correct |
| 37 |
Correct |
4 ms |
512 KB |
Output is correct |
| 38 |
Correct |
2 ms |
384 KB |
Output is correct |
| 39 |
Correct |
4 ms |
512 KB |
Output is correct |
| 40 |
Correct |
4 ms |
512 KB |
Output is correct |
| 41 |
Correct |
3 ms |
384 KB |
Output is correct |
| 42 |
Correct |
4 ms |
512 KB |
Output is correct |
| 43 |
Correct |
189 ms |
14424 KB |
Output is correct |
| 44 |
Correct |
1091 ms |
68876 KB |
Output is correct |
| 45 |
Correct |
651 ms |
26488 KB |
Output is correct |
| 46 |
Correct |
67 ms |
2808 KB |
Output is correct |
| 47 |
Correct |
685 ms |
39160 KB |
Output is correct |
| 48 |
Correct |
1226 ms |
104952 KB |
Output is correct |
| 49 |
Correct |
302 ms |
28784 KB |
Output is correct |
| 50 |
Correct |
1630 ms |
123292 KB |
Output is correct |
| 51 |
Correct |
689 ms |
48156 KB |
Output is correct |
| 52 |
Correct |
1415 ms |
106232 KB |
Output is correct |
| 53 |
Correct |
1350 ms |
98488 KB |
Output is correct |
| 54 |
Correct |
3 ms |
384 KB |
Output is correct |
| 55 |
Correct |
568 ms |
59520 KB |
Output is correct |
| 56 |
Correct |
791 ms |
67440 KB |
Output is correct |
| 57 |
Correct |
636 ms |
57720 KB |
Output is correct |
| 58 |
Correct |
1154 ms |
97868 KB |
Output is correct |
| 59 |
Correct |
826 ms |
54136 KB |
Output is correct |
| 60 |
Correct |
2205 ms |
131564 KB |
Output is correct |
| 61 |
Correct |
2083 ms |
131580 KB |
Output is correct |
| 62 |
Correct |
2325 ms |
131192 KB |
Output is correct |
| 63 |
Correct |
2232 ms |
131548 KB |
Output is correct |
| 64 |
Correct |
2080 ms |
131484 KB |
Output is correct |
| 65 |
Correct |
1876 ms |
131724 KB |
Output is correct |
| 66 |
Correct |
1938 ms |
131736 KB |
Output is correct |
| 67 |
Correct |
1585 ms |
131704 KB |
Output is correct |
| 68 |
Correct |
824 ms |
69508 KB |
Output is correct |
| 69 |
Correct |
782 ms |
63312 KB |
Output is correct |
| 70 |
Correct |
905 ms |
85204 KB |
Output is correct |
| 71 |
Correct |
1160 ms |
94128 KB |
Output is correct |
