oj.uz

Submission #541616

# Submission time Handle Problem Language Result Execution time Memory
541616 2022-03-23T21:31:17 Z bigg Teams (CEOI11_tea) C++14
100 / 100
 593 ms 129728 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4156 KB Output is correct
3 Correct 2 ms 4152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 4 ms 4308 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6500 KB Output is correct
2 Correct 23 ms 6412 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6772 KB Output is correct
2 Correct 23 ms 6632 KB Output is correct
3 Correct 29 ms 6776 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 25316 KB Output is correct
2 Correct 205 ms 26344 KB Output is correct
3 Correct 241 ms 26820 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 32752 KB Output is correct
2 Correct 593 ms 129728 KB Output is correct
3 Correct 273 ms 33228 KB Output is correct
4 Correct 289 ms 29360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 33720 KB Output is correct
2 Correct 218 ms 34676 KB Output is correct
3 Correct 270 ms 31508 KB Output is correct
4 Correct 329 ms 32832 KB Output is correct