Submission #1226839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226839		tgirolami09	Let's Win the Election (JOI22_ho_t3)	C++20	23 / 100	2596 ms	412 KiB

Main

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

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

using namespace std;

struct group{
    int first,second;
};

const bool compareSecond (group a, group b){
    if (a.second==b.second){
        return a.first<b.first;
    }
    else{
        return a.second<b.second;
    }
}

// void printVec(vector<group> v){
//     for (auto i : v){
//         printf("{%d,%d}, ",i.first,i.second);
//     }
//     printf("\n");
// }

int main(){
    int nbStates;
    int nbVotesNeeded;
    scanf("%d",&nbStates);
    scanf("%d",&nbVotesNeeded);

    vector<group> states;

    for (int i = 0;i<nbStates;++i){
        int vote,help;
        scanf("%d %d",&vote,&help);

        states.push_back({vote,help});
    }

    sort(states.begin(),states.end(),compareSecond);

    // printVec(states);

    double bestTime = (1 << 30);
    for (u_int32_t mask = 0;mask<(1<<nbStates);++mask){
        if (__popcount(mask) > nbVotesNeeded){
            continue;
        }

        // printf("Doing mask %d\n",mask);
        vector<int> votes;

        double currTime = 0;
        int currVotes = 0;
        int currHelpers = 1;
        for (int i = 0;i<nbStates;++i){
            if (mask & (1<<i) and states[i].second!=-1){
                // printf("\t %d is set\n",i);
                currTime += 1.0*states[i].second/(1.0*currHelpers);
                ++currVotes;
                ++currHelpers;
            }
                
            else{
                votes.push_back(states[i].first);
            }
        }

        if (currVotes<nbVotesNeeded){
            sort(votes.begin(),votes.end());
            int timeToadd = 0;
            for (int i = 0;i<nbVotesNeeded-currVotes;++i){
                timeToadd+=votes[i];
            }
            currTime += 1.0*timeToadd/(1.0*currHelpers);
        }

        // if (currTime<bestTime){
        //     bestTime = currTime;
        //     // printf("Best time with mask %d\n",(int)mask);
        // }
        bestTime = min(bestTime,currTime);
    }

    printf("%.3f\n",bestTime);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d",&nbStates);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d",&nbVotesNeeded);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d %d",&vote,&help);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23