Submission #1213861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213861		tgirolami09	Grudanje (COCI19_grudanje)	C++20	70 / 70	177 ms	22696 KiB

grudanje

#pragma GCC optimize("O2,unroll-loops")

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int treeSize = (1<<18); //Power of 2

//Root at 1
int segTree[treeSize][26] = {0};

int padding = (treeSize/2);

//Adds amount to the letter index from the index (included) to the end
void addLetterFromIndex(int letter, int amount, int index, int currNode, int NodeRangeLeft, int NodeRangeRight){
    if (index<=NodeRangeLeft){
        // printf("Added %d to tree index %d (range %d-%d)\n",amount,currNode, NodeRangeLeft, NodeRangeRight);
        segTree[currNode][letter]+=amount;
        return;
    }

    if (NodeRangeRight<index){
        return;
    }

    else{
        int middle = NodeRangeLeft+((NodeRangeRight-NodeRangeLeft)/2);
        addLetterFromIndex(letter, amount, index, currNode*2, NodeRangeLeft, middle);
        addLetterFromIndex(letter, amount, index, currNode*2+1, middle+1, NodeRangeRight);
    }
}

//Index must be 0-indexed and from original array
int letterAtIndex(int index, int letterIdx){
    int letterAmount = 0;

    int visiting = index+padding;
    bool visited1 = false;
    while (!visited1){
        letterAmount += segTree[visiting][letterIdx];

        if (visiting==1){
            visited1 = true;
        }
        visiting/=2;
    }

    return letterAmount;
}

//Returns last wrong letter (if 26 then word is correct)
int checkInterval(int left, int right, int lastWrong, int maxLetterIdx){
    for (int i = lastWrong;i<maxLetterIdx+1;++i){
        int leftLetterCount = 0;
        if (left!=0){
            leftLetterCount = letterAtIndex(left-1,i);
        }
        int rightLetterCount = letterAtIndex(right,i);
        if (abs(leftLetterCount-rightLetterCount)>1){
            return i;
            break;
        }
    }
    // printf("Interval %d-%d is correct\n",left,right);
    return 26;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string word;
    getline(cin,word);
    int nbIntervals;
    cin >> nbIntervals;

    int lowestSeenLetter = 25;
    int highestSeenLetter = 0;


    //Intervals are inclusive on both sides (but 1-indexed)
    vector<pair<int,int> > intervals;
    int longestInterval = 0;
    for (int i = 0; i<nbIntervals;++i){
        int start,end;
        cin >> start >> end;
        //Add them 0-indexed
        intervals.push_back({start-1,end-1});
        longestInterval = max(longestInterval,end-start+1);
    }
    // printf("Got intervals\n");

    vector<int> snowballOrder;
    for (int i = 0;i<word.size();++i){
        int target;
        cin >> target;
        snowballOrder.push_back(target);
    }
    // printf("Got snowballOrder\n");

    for (int i = 0;i<word.size();++i){
        char c = word[i];
        lowestSeenLetter = min(lowestSeenLetter,c-'a');
        highestSeenLetter = max(highestSeenLetter,c-'a');
        // printf("Adding %c to tree\n",c);
        addLetterFromIndex(c-'a',1,i,1,0,padding-1);
    }

    int minSnowBallsForCorrect = longestInterval-26;
    bool totalWordIsGood = false;
    int firstUnvalidIntervalIdx = 0;
    int firstUnvalidLetterIdx = lowestSeenLetter;

    if (minSnowBallsForCorrect<0){
        bool allIntervals = true;
        for (int i = firstUnvalidIntervalIdx; i<nbIntervals; ++i){
            pair<int,int> interval = intervals[i];
            int currFirstUnvalidLetter = checkInterval(interval.first, interval.second, firstUnvalidLetterIdx, highestSeenLetter);
            if (currFirstUnvalidLetter != 26){
                allIntervals = false;
                firstUnvalidIntervalIdx = i;
                firstUnvalidLetterIdx = currFirstUnvalidLetter;
                break;
            }
            else{
                // printf("Interval %d-%d is valid\n",interval.first,interval.second);
            }
        }

        if (allIntervals){
            printf("0\n");
            return 0;
        }
    }

    for (int SnowballIdx = 0;SnowballIdx<word.size();++SnowballIdx){
        // printf("Snowball %d : \n",SnowballIdx+1);
        int idx = snowballOrder[SnowballIdx];
        char letterHit = word[idx-1];
        addLetterFromIndex(letterHit-'a',-1,idx-1,1,0,padding-1);

        //Check that enough snow balls have hit and that the last snowball covered the blocking letter
        if (minSnowBallsForCorrect<=SnowballIdx+1){ //(letterHit-'a' == firstUnvalidLetterIdx) && 
            bool remainingIntervals = true;
            for (int i = firstUnvalidIntervalIdx; i<nbIntervals; ++i){
                pair<int,int> interval = intervals[i];
                int remainingIntervalsFirstUnvalidLetter = checkInterval(interval.first, interval.second, firstUnvalidLetterIdx, highestSeenLetter);
                if (remainingIntervalsFirstUnvalidLetter != 26){
                    remainingIntervals = false;
                    firstUnvalidIntervalIdx = i;
                    firstUnvalidLetterIdx = remainingIntervalsFirstUnvalidLetter;
                    break;
                }
                else{
                    // printf("Interval %d-%d is valid\n",interval.first,interval.second);
                    //Word is right so firstUnvalidLetterIdx is 0
                    firstUnvalidLetterIdx = lowestSeenLetter;
                }
            }

            if (remainingIntervals){
                printf("%d\n",SnowballIdx+1);
                return 0;
            }
        }
    }
    printf("Impossible\n");
}

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