Submission #1167750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167750		tgirolami09	Snowball (JOI21_ho_t2)	C++20	100 / 100	88 ms	9844 KiB

Main

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

#define int long long

using namespace std;

struct segment{
    int id; //Determine the snowballs before and after
    int length; //For calculations

    bool operator<(const segment& other)const{
        return length<other.length;
    }
};

void printSeg(segment s){
    printf("%lld : length %lld\n",s.id,s.length);
}

void printVec(vector<segment> v){
    for (segment s : v){
        printSeg(s);
    }
}

void printSol(vector<int> v){
    for (int i : v){
        printf("%lld\n",i);
    }
}

signed main(){
    int nbSnowballs,nbDays;
    scanf("%lld %lld",&nbSnowballs,&nbDays);
    vector<int> snowballPositions;
    int pos;
    for (int i = 0;i<nbSnowballs;++i){
        scanf("%lld",&pos);
        snowballPositions.push_back(pos);
    }

    vector<segment> segments;
    for (int i = 1;i<nbSnowballs;++i){
        segments.push_back({i-1,snowballPositions[i]-snowballPositions[i-1]});
    }

    sort(segments.begin(),segments.end());

    int minPos = 0;
    int maxPos = 0;
    int wind;
    int currentWind = 0;
    int firstPossible = 0;
    vector<int> answer(nbSnowballs,0);
    for (int i = 0;i<nbDays;++i){
        scanf("%lld",&wind);
        currentWind+=wind;
        if (currentWind>maxPos){
            //printf("New maximum to the right %lld\n",currentWind);
            for (int idx = firstPossible;idx<nbSnowballs-1;++idx){
                //Look at the smallest segment that can still alocate
                if (segments[idx].length>currentWind-minPos){
                    //Is the segment larger than the currentMax to the right and (substract because negative) the currentax to the left
                    break;
                }
                else{
                    //Segment is too small to alocate more

                    //Amount left that can be allocated
                    int canAllocate = segments[idx].length-(maxPos-minPos);

                    //allocating

                    //To the left (negative)
                    answer[segments[idx].id]+= (maxPos+canAllocate);

                    //To the right (positive)
                    answer[segments[idx].id+1]+= (-minPos);

                    ++firstPossible;
                }

            }
            maxPos = currentWind;
        }

        else if (currentWind<minPos){
            //printf("New maximum to the left %lld\n",currentWind);
            for (int idx = firstPossible;idx<nbSnowballs-1;++idx){
                //Look at the smallest segment that can still alocate
                if (segments[idx].length>maxPos-currentWind){
                    //The segment is larger than the currentMax to the right and (substract because negative) the currentax to the left
                    break;
                }
                else{
                    //Segment is too small to alocate more

                    //Amount left that can be allocated
                    int canAllocate = segments[idx].length-(maxPos-minPos);

                    //allocating

                    //To the left (negative)
                    answer[segments[idx].id]+= (maxPos);

                    //To the right (positie)
                    answer[segments[idx].id+1]+= (-minPos+canAllocate);

                    ++firstPossible;
                }

            }
            minPos = currentWind;
        }
    
    }
    //Finish for semgents larger at the end
    for (int idx = firstPossible;idx<nbSnowballs-1;++idx){
        //allocating

        //To the left (negative)
        answer[segments[idx].id]+= (maxPos);

        //To the right (positie)
        answer[segments[idx].id+1]+= (-minPos);

        ++firstPossible;
    }

    answer[0]+=(-minPos);
    answer[nbSnowballs-1]+=(maxPos);
    printSol(answer);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%lld %lld",&nbSnowballs,&nbDays);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%lld",&pos);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%lld",&wind);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67