| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 163067 | 2019-11-11T10:17:17 Z | georgerapeanu | Naan (JOI19_naan) | C++11 | 1122 ms | 3768 KB |
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 2000;
const int LMAX = 2000;
int n,l;
int v[NMAX + 5][LMAX + 5];
bool taken[NMAX + 5];
int perm[NMAX + 5];
long long gcd(long long a,long long b){
if(b == 0){
return a;
}
return gcd(b,a % b);
}
struct frac_t{
long long p,q;
long long num;
frac_t(long long val = 0){
this->p = 0;
this->q = 1;
this->num = val;
}
frac_t operator + (const frac_t &other)const{
frac_t ans;
ans.num = this->num + other.num;
ans.q = this->q * other.q;
ans.p = this->p * other.q + other.p * this->q;
long long g = gcd(ans.p,ans.q);
ans.p /= g;
ans.q /= g;
ans.num += ans.p / ans.q;
ans.p %= ans.q;
return ans;
}
frac_t operator - (const frac_t &other)const{
frac_t ans;
ans.num = this->num - other.num;
ans.q = this->q * other.q;
ans.p = this->p * other.q - other.p * this->q;
if(ans.p < 0){
ans.num += (ans.p / ans.q - 1);
ans.p -= ans.q * (ans.p / ans.q - 1);
}
ans.num += ans.p / ans.q;
ans.p %= ans.q;
long long g = gcd(ans.p,ans.q);
ans.p /= g;
ans.q /= g;
return ans;
}
frac_t operator * (const frac_t &other)const{
frac_t a = *this;
frac_t b = other;
a.p += a.q * a.num;
b.p += b.q * b.num;
long long g1 = gcd(a.p,b.q);
a.p /= g1;
b.q /= g1;
long long g2 = gcd(a.q,b.p);
a.q /= g2;
b.p /= g2;
frac_t ans;
ans.p = a.p * b.p;
ans.q = a.q * b.q;
ans.num = ans.p / ans.q;
ans.p %= ans.q;
return ans;
}
frac_t operator / (const frac_t &other)const{
frac_t a = *this;
frac_t b = other;
a.p += a.q * a.num;
b.p += b.q * b.num;
swap(b.p,b.q);
long long g1 = gcd(a.p,b.q);
a.p /= g1;
b.q /= g1;
long long g2 = gcd(a.q,b.p);
a.q /= g2;
b.p /= g2;
frac_t ans;
ans.p = a.p * b.p;
ans.q = a.q * b.q;
ans.num = ans.p / ans.q;
ans.p %= ans.q;
return ans;
}
bool operator <= (const frac_t &other)const{///HOPE no overflow
if(this-> num != other.num){
return this->num < other.num;
}
return this->p * other.q <= other.p * this->q;
}
};
frac_t lst_cost[NMAX + 5];
frac_t target_cost[NMAX + 5];
frac_t split[NMAX + 5];
int main(){
scanf("%d %d",&n,&l);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= l;j++){
scanf("%d",&v[i][j]);
target_cost[i] = target_cost[i] + frac_t(v[i][j]);
}
target_cost[i] = target_cost[i] / frac_t(n);
}
frac_t last_pos(0);
int cnt_splits = 0;
frac_t min_increment(0);
min_increment.p = 1;
min_increment.q = 2e8;
while(cnt_splits < n - 1){
frac_t min_nxt = last_pos + min_increment;
bool expand = false;
for(int i = 1;i <= n;i++){
if(taken[i]){
continue;
}
lst_cost[i] = lst_cost[i] + (frac_t(last_pos.num + 1) - last_pos) * frac_t(v[i][last_pos.num + 1]);
expand |= (target_cost[i] <= lst_cost[i]);
}
last_pos.num++;
last_pos.p = 0;
last_pos.q = 1;
if(expand == false){
continue;
}
frac_t bst_frac;
int id = -1;
for(int i = 1;i <= n;i++){
if(taken[i]){
continue;
}
if(target_cost[i] <= lst_cost[i]){
frac_t tmp = (lst_cost[i] - target_cost[i]) / frac_t(v[i][last_pos.num]);
if(id == -1 || bst_frac <= tmp){
bst_frac = tmp;
id = i;
}
}
}
last_pos = last_pos - bst_frac;
if(last_pos <= min_nxt){
min_nxt = last_pos;
}
for(int i = 1;i <= n;i++){
if(taken[i]){
continue;
}
lst_cost[i] = frac_t(0);
}
split[++cnt_splits] = last_pos;
taken[id] = true;
perm[cnt_splits] = id;
}
for(int i = 1;i <= n;i++){
if(taken[i] == false){
perm[n] = i;
}
}
for(int i = 1;i < n;i++){
split[i].p += split[i].num * split[i].q;
split[i].num = 0;
printf("%lld %lld\n",split[i].p,split[i].q);
}
for(int i = 1;i <= n;i++){
printf("%d ",perm[i]);
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 504 KB | Output is correct |
| 2 | Correct | 3 ms | 504 KB | Output is correct |
| 3 | Correct | 3 ms | 504 KB | Output is correct |
| 4 | Correct | 3 ms | 504 KB | Output is correct |
| 5 | Correct | 3 ms | 504 KB | Output is correct |
| 6 | Correct | 2 ms | 504 KB | Output is correct |
| 7 | Correct | 3 ms | 504 KB | Output is correct |
| 8 | Correct | 2 ms | 504 KB | Output is correct |
| 9 | Correct | 2 ms | 504 KB | Output is correct |
| 10 | Correct | 3 ms | 504 KB | Output is correct |
| 11 | Correct | 3 ms | 504 KB | Output is correct |
| 12 | Correct | 3 ms | 504 KB | Output is correct |
| 13 | Correct | 3 ms | 504 KB | Output is correct |
| 14 | Correct | 3 ms | 504 KB | Output is correct |
| 15 | Correct | 3 ms | 504 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 504 KB | Output is correct |
| 2 | Correct | 3 ms | 504 KB | Output is correct |
| 3 | Correct | 4 ms | 504 KB | Output is correct |
| 4 | Correct | 4 ms | 504 KB | Output is correct |
| 5 | Correct | 4 ms | 504 KB | Output is correct |
| 6 | Correct | 8 ms | 556 KB | Output is correct |
| 7 | Correct | 3 ms | 504 KB | Output is correct |
| 8 | Correct | 3 ms | 504 KB | Output is correct |
| 9 | Correct | 5 ms | 504 KB | Output is correct |
| 10 | Correct | 5 ms | 504 KB | Output is correct |
| 11 | Correct | 4 ms | 504 KB | Output is correct |
| 12 | Correct | 14 ms | 504 KB | Output is correct |
| 13 | Correct | 3 ms | 504 KB | Output is correct |
| 14 | Correct | 5 ms | 504 KB | Output is correct |
| 15 | Correct | 4 ms | 504 KB | Output is correct |
| 16 | Correct | 5 ms | 504 KB | Output is correct |
| 17 | Correct | 5 ms | 504 KB | Output is correct |
| 18 | Correct | 5 ms | 504 KB | Output is correct |
| 19 | Correct | 5 ms | 504 KB | Output is correct |
| 20 | Correct | 5 ms | 504 KB | Output is correct |
| 21 | Correct | 5 ms | 504 KB | Output is correct |
| 22 | Correct | 5 ms | 504 KB | Output is correct |
| 23 | Correct | 2 ms | 504 KB | Output is correct |
| 24 | Correct | 4 ms | 504 KB | Output is correct |
| 25 | Correct | 4 ms | 504 KB | Output is correct |
| 26 | Correct | 3 ms | 504 KB | Output is correct |
| 27 | Correct | 4 ms | 504 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 504 KB | Output is correct |
| 2 | Correct | 3 ms | 504 KB | Output is correct |
| 3 | Correct | 3 ms | 504 KB | Output is correct |
| 4 | Correct | 3 ms | 504 KB | Output is correct |
| 5 | Correct | 3 ms | 504 KB | Output is correct |
| 6 | Correct | 2 ms | 504 KB | Output is correct |
| 7 | Correct | 3 ms | 504 KB | Output is correct |
| 8 | Correct | 2 ms | 504 KB | Output is correct |
| 9 | Correct | 2 ms | 504 KB | Output is correct |
| 10 | Correct | 3 ms | 504 KB | Output is correct |
| 11 | Correct | 3 ms | 504 KB | Output is correct |
| 12 | Correct | 3 ms | 504 KB | Output is correct |
| 13 | Correct | 3 ms | 504 KB | Output is correct |
| 14 | Correct | 3 ms | 504 KB | Output is correct |
| 15 | Correct | 3 ms | 504 KB | Output is correct |
| 16 | Correct | 3 ms | 504 KB | Output is correct |
| 17 | Correct | 3 ms | 504 KB | Output is correct |
| 18 | Correct | 4 ms | 504 KB | Output is correct |
| 19 | Correct | 4 ms | 504 KB | Output is correct |
| 20 | Correct | 4 ms | 504 KB | Output is correct |
| 21 | Correct | 8 ms | 556 KB | Output is correct |
| 22 | Correct | 3 ms | 504 KB | Output is correct |
| 23 | Correct | 3 ms | 504 KB | Output is correct |
| 24 | Correct | 5 ms | 504 KB | Output is correct |
| 25 | Correct | 5 ms | 504 KB | Output is correct |
| 26 | Correct | 4 ms | 504 KB | Output is correct |
| 27 | Correct | 14 ms | 504 KB | Output is correct |
| 28 | Correct | 3 ms | 504 KB | Output is correct |
| 29 | Correct | 5 ms | 504 KB | Output is correct |
| 30 | Correct | 4 ms | 504 KB | Output is correct |
| 31 | Correct | 5 ms | 504 KB | Output is correct |
| 32 | Correct | 5 ms | 504 KB | Output is correct |
| 33 | Correct | 5 ms | 504 KB | Output is correct |
| 34 | Correct | 5 ms | 504 KB | Output is correct |
| 35 | Correct | 5 ms | 504 KB | Output is correct |
| 36 | Correct | 5 ms | 504 KB | Output is correct |
| 37 | Correct | 5 ms | 504 KB | Output is correct |
| 38 | Correct | 2 ms | 504 KB | Output is correct |
| 39 | Correct | 4 ms | 504 KB | Output is correct |
| 40 | Correct | 4 ms | 504 KB | Output is correct |
| 41 | Correct | 3 ms | 504 KB | Output is correct |
| 42 | Correct | 4 ms | 504 KB | Output is correct |
| 43 | Incorrect | 1122 ms | 3768 KB | Integer parameter [name=A_i] equals to 2135845198282, violates the range [1, 2000000000000] |
| 44 | Halted | 0 ms | 0 KB | - |