# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
699173 |
2023-02-15T23:23:41 Z |
doowey |
Naan (JOI19_naan) |
C++14 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2010;
struct frac{
ll A;
ll B;
void normalize(){
ll g = __gcd(A, B);
A /= g;
B /= g;
}
frac operator+ (frac y){
frac T = {A * y.B + B * y.A, B * y.B};
T.normalize();
return T;
}
frac operator- (frac y){
frac T = {A * y.B - B * y.A, B * y.B};
T.normalize();
return T;
}
bool operator< (frac y){
return (A * y.B - B * y.A < 0);
}
};
ll V[N][N];
ll S[N][N];
int m;
frac calc(int id, frac P){
int las = P.A / P.B;
frac Y = {S[id][las], 1};
frac add = (P - (frac){las, 1});
add.A *= V[id][las + 1];
Y = Y + add;
return Y;
}
frac need[N];
bool use[N];
int pi[N];
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
int n;
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
need[i] = {0, n};
for(int j = 1; j <= m ; j ++ ){
cin >> V[i][j];
need[i].A += V[i][j];
S[i][j] = V[i][j] + S[i][j - 1];
}
pi[i] = -1;
}
frac las = {0, 1};
frac tis;
frac nx;
frac cur;
frac low;
int idx;
frac S;
ll X;
for(int it = 1; it < n; it ++ ){
low = {m, 1};
idx = -1;
for(int i = 1; i <= n; i ++ ){
if(!use[i]){
tis = calc(i, las);
for(int j = 1; j <= m; j ++ ){
nx = calc(i, {j, 1});
if(need[i] < nx - tis){
S = nx - tis;
S = S - need[i];
S.A *= (ll)n;
X = S.A / S.B;
tis = (frac){j, 1} - (frac){X, n * 1ll * V[i][j]};
if(tis < low){
low = tis;
idx = i;
}
break;
}
}
}
}
pi[it] = idx;
use[idx]=true;
las = low;
cout << low.A << " " << low.B << "\n";
}
for(int i = 1; i <= n; i ++ ){
if(!use[i]){
pi[n]=i;
}
}
for(int i = 1; i <= n; i ++ ){
cout << pi[i] << " ";
}
cout << "\n";
return 0;
}
Compilation message
naan.cpp: In function 'int main()':
naan.cpp:72:10: warning: unused variable 'cur' [-Wunused-variable]
72 | frac cur;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
X_i is not increasing |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Incorrect |
1 ms |
340 KB |
X_i is not increasing |
18 |
Halted |
0 ms |
0 KB |
- |