Submission #1167750

#TimeUsernameProblemLanguageResultExecution timeMemory
1167750tgirolami09Snowball (JOI21_ho_t2)C++20
100 / 100
88 ms9844 KiB
#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);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...