Submission #541616

#TimeUsernameProblemLanguageResultExecution timeMemory
541616biggTeams (CEOI11_tea)C++14
100 / 100
593 ms129728 KiB
#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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...