| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 247255 | SomeoneUnknown | Wine Tasting (FXCUP4_wine) | C++17 | 15 ms | 1020 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;
struct b13{
vector<int> digits;
void carry_over(){
for(int i = 0; i < digits.size(); i++){
digits.push_back(0);
digits[i+1] += digits[i]/13;
digits[i] %= 13;
//printf("%d ", digits.back());
if(digits.back() == 0) digits.pop_back();
}
//printf("\n");
}
b13(){
}
b13(int sval){
digits.push_back(sval);
carry_over();
}
};
b13* ad13(b13 *a, b13 *b){
b13 *res = new b13(0);
int i;
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
res->digits.push_back(a->digits[i]+b->digits[i]);
}
for(; i < a->digits.size(); ++i){
res->digits.push_back(a->digits[i]);
}
for(; i < b->digits.size(); ++i){
res->digits.push_back(b->digits[i]);
}
res->carry_over();
return res;
}
b13* mp13(b13 *a, b13 *b){
b13 *res = new b13(0);
for(int i = 0; i < a->digits.size(); ++i){
for(int j = 0; j < b->digits.size(); ++j){
if(i+j >= res->digits.size()){
res->digits.push_back(0);
}
res->digits[i+j] += a->digits[i] * b->digits[j];
}
}
res->carry_over();
while(res->digits.back() == 0){
res->digits.pop_back();
}
return res;
}
b13* sb13(b13 *a, b13 *b){ //will throw an error if this results in a negative number!
b13 *res = new b13(0);
int i;
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
res->digits.push_back(a->digits[i]-b->digits[i]);
}
for(; i < a->digits.size(); ++i){
res->digits.push_back(a->digits[i]);
}
for(int i = 0; i < res->digits.size(); ++i){
while(res->digits[i] < 0){
res->digits[i] += 13;
res->digits[i+1] -= 1;
}
}
return res;
}
vector<int> BlendWines(int K, vector<int> R){
int N = R.size();
vector<b13*> factorials;
factorials.push_back(new b13(1));
for(int i = 1; i <= N; i++){
factorials.push_back(mp13(factorials.back(), new b13(i)));
}
bool unused[N+1];
for(int i = 0; i < N+1; ++i) unused[i] = true;
b13 *pno = new b13(0);
for(int i = 0; i < N; ++i){
int afterunused = 0;
unused[R[i]] = false;
for(int j = 1; j < R[i]; ++j){
if(unused[j]) ++afterunused;
}
b13 *psubt = mp13(factorials[N-1-i], new b13(afterunused));
pno = ad13(pno, psubt);
}
vector<int> res;
for(int i = 0; i < N; i++){
if(i > pno->digits.size()){
res.push_back(1);
}else{
res.push_back(pno->digits[i]+1);
}
}
return res;
}
#include "taster.h"
#include <bits/stdc++.h>
using namespace std;
struct b13{
vector<int> digits;
void carry_over(){
for(int i = 0; i < digits.size(); i++){
digits.push_back(0);
digits[i+1] += digits[i]/13;
digits[i] %= 13;
//printf("%d ", digits.back());
if(digits.back() == 0) digits.pop_back();
}
//printf("\n");
}
b13(){
}
b13(int sval){
digits.push_back(sval);
carry_over();
}
};
b13* ad13(b13 *a, b13 *b){
b13 *res = new b13(0);
int i;
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
res->digits.push_back(a->digits[i]+b->digits[i]);
}
for(; i < a->digits.size(); ++i){
res->digits.push_back(a->digits[i]);
}
for(; i < b->digits.size(); ++i){
res->digits.push_back(b->digits[i]);
}
res->carry_over();
return res;
}
b13* mp13(b13 *a, b13 *b){
b13 *res = new b13(0);
for(int i = 0; i < a->digits.size(); ++i){
for(int j = 0; j < b->digits.size(); ++j){
if(i+j >= res->digits.size()){
res->digits.push_back(0);
}
res->digits[i+j] += a->digits[i] * b->digits[j];
}
}
res->carry_over();
while(res->digits.back() == 0){
res->digits.pop_back();
}
return res;
}
b13* sb13(b13 *a, b13 *b){ //will throw an error if this results in a negative number!
b13 *res = new b13(0);
int i;
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
res->digits.push_back(a->digits[i]-b->digits[i]);
}
for(; i < a->digits.size(); ++i){
res->digits.push_back(a->digits[i]);
}
for(int i = 0; i < res->digits.size(); ++i){
while(res->digits[i] < 0){
res->digits[i] += 13;
res->digits[i+1] -= 1;
}
}
return res;
}
bool agthanb(b13 *a, b13 *b){
while(a->digits.back() == 0){
a->digits.pop_back();
}
while(b->digits.back() == 0){
b->digits.pop_back();
}
if(a->digits.size() > b->digits.size()){
return true;
}
if(a->digits.size() < b->digits.size()){
return false;
}
for(int i = a->digits.size()-1; i >= 0; --i){
if(a->digits[i] > b->digits[i]){
return true;
}
if(a->digits[i] < b->digits[i]){
return false;
}
}
return false;
}
vector<int> SortWines(int K, vector<int> A) {
int N = A.size();
vector<b13*> factorials;
factorials.push_back(new b13(1));
for(int i = 1; i <= N; i++){
factorials.push_back(mp13(factorials.back(), new b13(i)));
}
vector<int> res;
b13 *pno = new b13();
for(int i = 0; i < N; i++){
pno->digits.push_back(A[i]-1);
}
vector<int> r;
bool used[N+1];
for(int i = 0; i <= N; ++i) used[i] = false;
for(int i = 0; i < N; i++){
int curval = 1;
while(used[curval]) ++curval;
while(!agthanb(factorials[N-1-i], pno)){
pno = sb13(pno, factorials[N-1-i]);
++curval;
while(used[curval]) ++curval;
}
r.push_back(curval);
}
//Compare(1, 2);
return r;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||