Submission #904317

#	Time	Username	Problem	Language	Result	Execution time	Memory
904317		qqspeed20015	Gauss (COCI17_gauss)	C++17	160 / 160	1684 ms	126868 KiB

gauss

#include <bits/stdc++.h>
using namespace std;

int MAX = 1e6, MAX_SUM_EXP = 20;
vector <int> numDivisor(MAX + 1, 0);
vector <int> sumExponent(MAX + 1, 0);
const int INF = 1e9 + 20;

void sieve() {
    for (int divisor = 1; divisor <= MAX; divisor++) {
        for (int multiplier = divisor; multiplier <= MAX; multiplier += divisor) {
            numDivisor[multiplier] += 1;
            if (numDivisor[divisor] == 2) {
                int temp = multiplier;
                do {
                    sumExponent[multiplier]++;
                    temp /= divisor;
                } while (temp % divisor == 0);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int k;
    cin >> k;
    vector <int> listPricePath(k);
    for (int i = 0; i < k; i++)
        cin >> listPricePath[i];
    
    int numQueriesLength;
    cin >> numQueriesLength;
    vector <int> listLength(numQueriesLength);
    for (int indexOfLength = 0; indexOfLength < numQueriesLength; indexOfLength++)
        cin >> listLength[indexOfLength];

    int numQueriesLuckyNumber;
    cin >> numQueriesLuckyNumber;
    vector <int> listLuckyNumber(numQueriesLuckyNumber);
    vector <int> listCostLuckyNumber(numQueriesLuckyNumber);
    for (int indexOfLuckyNumber = 0; indexOfLuckyNumber < numQueriesLuckyNumber; indexOfLuckyNumber++)
        cin >> listLuckyNumber[indexOfLuckyNumber] >> listCostLuckyNumber[indexOfLuckyNumber];
    
    sieve();    
    // shortestPathTo1[i][j] = Shortest path from i to 1 known that sum of exp = j
    vector <vector <int>> shortestPathTo1(MAX + 1, vector <int> (MAX_SUM_EXP + 2, INF));
    shortestPathTo1[1][0] = 0;
    for (int divisor = 1; divisor <= MAX; divisor++) {
        for (int multiplier = 2 * divisor, base = 2; multiplier <= MAX; multiplier += divisor, base++) {
            for (int sumOfExp = 0; sumOfExp <= sumExponent[divisor]; sumOfExp++)
                shortestPathTo1[multiplier][sumOfExp + 1]
                = min(shortestPathTo1[multiplier][sumOfExp + 1],
                    shortestPathTo1[divisor][sumOfExp] + (numDivisor[base] <= k ? listPricePath[numDivisor[base] - 1] : 0));
        }      
    }

    int numQueriesAnswer, firstNumber, secondNumber;
    cin >> numQueriesAnswer;
    for (int indexOfQueries = 1; indexOfQueries <= numQueriesAnswer; indexOfQueries++) {
        cin >> firstNumber >> secondNumber;
        if (firstNumber % secondNumber != 0) {
            cout << (-1 * numQueriesLength);
            continue;
        }
        int compressSource = firstNumber / secondNumber;
        // d(A, B) = d(A / B, 1) without using option 2: Leave with lucky number
        // shortestPathWithoutLuckyNumber[j] = Shortest path from A / B to 1 known that sum of exp = j
        vector <int> shortestPathWithoutLuckyNumber(MAX_SUM_EXP + 2, 0); // base2
        for (int sumOfExp = 1; sumOfExp <= sumExponent[compressSource]; sumOfExp++)
            shortestPathWithoutLuckyNumber[sumOfExp] = shortestPathTo1[compressSource][sumOfExp];
        // shortestPathLuckyNumber[j] = Shortest path from A to B known that sum of exp = j using lucky number
        vector <int> shortestPathLuckyNumber(numQueriesLuckyNumber + 1, INF); // base3
        // canUseCost: The array list all cost can use for optimization path
        vector <int> canUseCost;
        for (int indexOfLuckyNumber = 0; indexOfLuckyNumber < numQueriesLuckyNumber; indexOfLuckyNumber++) {
            // The other way is using one lucky number for immediate point
            // A --> X --> B, X is lucky number
            if ((firstNumber % listLuckyNumber[indexOfLuckyNumber] != 0) || (listLuckyNumber[indexOfLuckyNumber] % secondNumber != 0))
                continue;
            int compressAX = firstNumber / listLuckyNumber[indexOfLuckyNumber];
            int compressBX = listLuckyNumber[indexOfLuckyNumber] / secondNumber;

            // shortestPathImmediate[j] = Shortest path from A to B known that sum of exp = j and must through lucky number
            vector <int> shortestPathImmediate(MAX_SUM_EXP + 2, INF); // base1

            for (int sumOfExpAX = 0; sumOfExpAX <= sumExponent[compressAX]; sumOfExpAX++) {
                for (int sumOfExpBX = 0; sumOfExpBX <= sumExponent[compressBX]; sumOfExpBX++) {
                    shortestPathImmediate[sumOfExpAX + sumOfExpBX]
                    = min(shortestPathImmediate[sumOfExpAX + sumOfExpBX],
                        shortestPathTo1[compressAX][sumOfExpAX] + shortestPathTo1[compressBX][sumOfExpBX]);
                }
            }

            shortestPathLuckyNumber[indexOfLuckyNumber] = INF;
            for (int sumOfExp = 0; sumOfExp <= sumExponent[compressSource]; sumOfExp++) {
                shortestPathLuckyNumber[indexOfLuckyNumber] 
                = min(shortestPathLuckyNumber[indexOfLuckyNumber] + listCostLuckyNumber[indexOfLuckyNumber],
                    shortestPathImmediate[sumOfExp]);
                shortestPathWithoutLuckyNumber[sumOfExp]
                = min(shortestPathWithoutLuckyNumber[sumOfExp], shortestPathLuckyNumber[indexOfLuckyNumber]);
            }

            if (shortestPathLuckyNumber[indexOfLuckyNumber] != INF)
                canUseCost.push_back(indexOfLuckyNumber);
        }
        long long res = 0;
		for (int indexOfLength = 0; indexOfLength < numQueriesLength; indexOfLength++) {
			if (listLength[indexOfLength] <= sumExponent[compressSource]) {
				if (shortestPathWithoutLuckyNumber[listLength[indexOfLength]] == INF)
					res -= 1;
				else
					res += shortestPathWithoutLuckyNumber[listLength[indexOfLength]];
			}
			else {
				int cur = INF;
				for (auto &id: canUseCost) {
                    // Let's go over all possible lucky number and look at the formula 
                    // for the total number of moves L, and denote with L' the number of moves
                    // when we leave C on the board:
					cur = min(cur, (listLength[indexOfLength] - sumExponent[compressSource]) * listCostLuckyNumber[id] + shortestPathLuckyNumber[id]);
				}
				if (cur == INF)
					res += -1;
				else
					res += cur;
			}
		}
		cout << res << '\n';
    }
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16