답안 #247370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247370 2020-07-11T09:03:09 Z SomeoneUnknown 포도주 시음 (FXCUP4_wine) C++17
0 / 100
5 ms 1020 KB
#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) {
  return 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 -