#include "bartender.h"
#include <bits/stdc++.h>
using namespace std;
struct bthirteen{
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");
}
bthirteen(){
}
bthirteen(int sval){
digits.push_back(sval);
carry_over();
}
};
bthirteen* ad13(bthirteen *a, bthirteen *b){
bthirteen *res = new bthirteen();
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;
}
bthirteen* mp13(bthirteen *a, bthirteen *b){
bthirteen *res = new bthirteen(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;
}
bthirteen* sbthirteen(bthirteen *a, bthirteen *b){ //will throw an error if this results in a negative number!
bthirteen *res = new bthirteen();
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<bthirteen*> factorials;
factorials.push_back(new bthirteen(1));
for(int i = 1; i <= N; i++){
factorials.push_back(mp13(factorials.back(), new bthirteen(i)));
}
bool unused[N+1];
for(int i = 0; i < N+1; ++i) unused[i] = true;
bthirteen *pno = new bthirteen(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;
}
bthirteen *psubt = mp13(factorials[N-1-i], new bthirteen(afterunused));
/*printf("psubt: ");
for(int i = 0; i < psubt->digits.size(); ++i){
printf("%d ", psubt->digits[i]);
}
printf("\n");//*/
pno = ad13(pno, psubt);
/*printf("Calculating: ");
for(int i = 0; i < pno->digits.size(); ++i){
printf("%d ", pno->digits[i]);
}
printf("\n");//*/
}
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);
}
}
/*for(int i = 0; i < pno->digits.size(); ++i){
printf("%d ", pno->digits[i]);
}
printf("\n");
for(int i = 0; i < res.size(); ++i){
printf("%d ", res[i]);
}
printf("\n");
//printf("Hello world.\n");//*/
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();
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!
/*printf("sb in: ");
for(int i = 0; i < min(5, (int)a->digits.size()); ++i){
printf("%d ", a->digits[i]);
}
printf("- ");
for(int i = 0; i < min(5, (int)b->digits.size()); ++i){
printf("%d ", b->digits[i]);
}//*/
b13 *res = new b13();
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();
}
//printf("%d %d\n", a->digits.size(), b->digits.size());
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);
//printf("%d", 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;
//printf("pno digits: %d\n", pno->digits.size());
while(!agthanb(factorials[N-1-i], pno)){
//printf("pno: %d. factorial: %d\n", pno->digits.size(), factorials[N-1-i]->digits.size());
pno = sb13(pno, factorials[N-1-i]);
++curval;
//printf("increasing curval at %d\n", i);
while(used[curval]) ++curval;
}
r.push_back(curval);
used[curval] = true;
}
//Compare(1, 2);
return r;
}
Compilation message
bartender.cpp: In member function 'void bthirteen::carry_over()':
bartender.cpp:9:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < digits.size(); i++){
~~^~~~~~~~~~~~~~~
bartender.cpp: In function 'bthirteen* ad13(bthirteen*, bthirteen*)':
bartender.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bartender.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i < a->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
bartender.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i < b->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
bartender.cpp: In function 'bthirteen* mp13(bthirteen*, bthirteen*)':
bartender.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
bartender.cpp:48:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < b->digits.size(); ++j){
~~^~~~~~~~~~~~~~~~~~
bartender.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+j >= res->digits.size()){
~~~~^~~~~~~~~~~~~~~~~~~~~
bartender.cpp: In function 'bthirteen* sbthirteen(bthirteen*, bthirteen*)':
bartender.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bartender.cpp:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i < a->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
bartender.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < res->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~~~
bartender.cpp: In function 'std::vector<int> BlendWines(int, std::vector<int>)':
bartender.cpp:111:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i > pno->digits.size()){
~~^~~~~~~~~~~~~~~~~~~~
taster.cpp: In member function 'void b13::carry_over()':
taster.cpp:9:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < digits.size(); i++){
~~^~~~~~~~~~~~~~~
taster.cpp: In function 'b13* ad13(b13*, b13*)':
taster.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
taster.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i < a->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
taster.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i < b->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
taster.cpp: In function 'b13* mp13(b13*, b13*)':
taster.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
taster.cpp:48:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < b->digits.size(); ++j){
~~^~~~~~~~~~~~~~~~~~
taster.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+j >= res->digits.size()){
~~~~^~~~~~~~~~~~~~~~~~~~~
taster.cpp: In function 'b13* sb13(b13*, b13*)':
taster.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < min(a->digits.size(), b->digits.size()); ++i){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
taster.cpp:76:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i < a->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~
taster.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < res->digits.size(); ++i){
~~^~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
1020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
