Submission #541616

#	Time	Username	Problem	Language	Result	Execution time	Memory
541616		bigg	Teams (CEOI11_tea)	C++14	100 / 100	593 ms	129728 KiB

tea

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

const int MAXN = 1e6 + 10;
const int INF = 1e9 + 7;
int n;
int dp[MAXN], pp[MAXN];
pair<int, int> kids[MAXN];
vector<vector<int> > team;

set<pair<int, int> > tam;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &kids[i].first);
        kids[i].second = i;
    }
    sort(kids + 1, kids + 1 + n);
    reverse(kids + 1, kids + 1 + n);

    
    memset(dp, -INF, sizeof(dp));
    dp[n + 1] = 0;
    for(int i = n; i > 0; i--){
        dp[i] = dp[i + 1];
        if(i + kids[i].first <= n + 1) dp[i] = max(dp[i], dp[i + kids[i].first] + 1);
        if(i == 1) dp[i] = dp[i + kids[i].first] + 1;
        if(i + kids[i].first <= n + 1 && dp[i] == dp[i + kids[i].first] + 1) pp[i] = i + kids[i].first;
        else pp[i] = i + 1;
    }

    for(int i = 1; i <= n; i++){
        int curkid = kids[i].second;
        int qnt = kids[i].first;
        if(pp[i] != i + qnt){
            int tamteam = tam.begin()->second;
            tam.erase(tam.begin());
            team[tamteam].push_back(curkid);
            tam.insert(make_pair(team[tamteam].size(), tamteam));
            continue;
        }

        team.push_back(vector<int> (1, curkid));
        int idx = team.size() - 1;
        while(--qnt) team[idx].push_back(kids[++i].second);
        tam.insert(make_pair(team[idx].size(), idx));
    
    }

    printf("%lu\n", team.size());
    for(int i = 0; i < team.size(); i++){
        printf("%lu ", team[i].size());
        sort(team[i].begin(), team[i].end());
        for(int j = 0; j < team[i].size(); j++) printf("%d ", team[i][j]);
        printf("\n");
    }
}

Compilation message (stderr)

tea.cpp: In function 'int main()':
tea.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < team.size(); i++){
      |                    ~~^~~~~~~~~~~~~
tea.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j = 0; j < team[i].size(); j++) printf("%d ", team[i][j]);
      |                        ~~^~~~~~~~~~~~~~~~
tea.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d", &kids[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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