| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 699359 |
2023-02-16T16:39:47 Z |
doowey |
Naan (JOI19_naan) |
C++14 |
|
0 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;
const ll C = (ll)1e18;
int cii;
int cjj;
struct frac{
ll A;
ll B;
frac operator+ (frac y){
if(A > C / y.B){
cout << "WA\n";
exit(0);
}
if(B > C / y.B){
cout << "WA\n";
exit(0);
}
return {A * y.B + B * y.A, B * y.B};
}
frac operator- (frac y){
if(A > C / y.B){
cout << "WA\n";
exit(0);
}
if(B > C / y.B){
cout << "WA\n";
exit(0);
}
return {A * y.B - B * y.A, B * y.B};
}
bool operator< (frac y){
if(A/B != y.A/y.B){
return A/B < y.A/y.B;
}
ll D = A/B;
ll temp0 = A - D * B;
ll temp1 = y.A - D * y.B;
return (temp0 * y.B - temp1 * B < 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;
int vv;
for(int i = 1; i <= n; i ++ ){
need[i] = {0, n};
for(int j = 1; j <= m ; j ++ ){
cin >> vv;
V[i][j] = vv;
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 SS;
ll X;
int pos;
for(int it = 1; it < n; it ++ ){
low = {m, 1};
idx = -1;
for(int i = 1; i <= n; i ++ ){
cii = i;
if(!use[i]){
tis = calc(i, las);
int j = 0;
int pp;
for(int ln = 10; ln >= 0; ln -- ){
pp = (j + (1 << ln));
if(pp <= m){
nx = (frac){S[i][pp], 1ll};
if(nx < tis) {
j = pp;
}
else{
SS = nx - tis;
SS = SS - need[i];
if(SS.A < 0){
j = pp;
}
}
}
}
j ++ ;
nx = (frac){S[i][j], 1ll};
if(tis < nx){
SS = nx - tis;
SS = SS - need[i];
if(SS.A > 0){
SS.B /= n;
X = SS.A / SS.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 << (long long)low.A << " " << (long long)low.B << "\n";
}
for(int i = 1; i <= n; i ++ ){
if(!use[i]){
pi[n]=i;
}
}
//return 0;
for(int i = 1; i <= n; i ++ ){
cout << pi[i] << " ";
}
cout << "\n";
return 0;
}
Compilation message
naan.cpp: In function 'int main()':
naan.cpp:91:10: warning: unused variable 'cur' [-Wunused-variable]
91 | frac cur;
| ^~~
naan.cpp:96:9: warning: unused variable 'pos' [-Wunused-variable]
96 | int pos;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
