답안 #247368

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

bartender.cpp: In member function 'void b13::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 'b13* ad13(b13*, b13*)':
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 'b13* mp13(b13*, b13*)':
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 'b13* sb13(b13*, b13*)':
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:101: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:65: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:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; i < a->digits.size(); ++i){
           ~~^~~~~~~~~~~~~~~~~~
taster.cpp:71: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 6 ms 1020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -