| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1111442 |
2024-11-12T08:31:34 Z |
Requiem |
Teams (CEOI11_tea) |
C++17 |
|
33 ms |
23120 KB |
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "divteam"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
ii dp[MAXN];
int n;
ii ord[MAXN];
ii trace[MAXN];
int numTeams = 0;
int bestTeam = 0;
int minSize = inf;
vector<int> teams[MAXN];
vector<int> ansTeams[MAXN];
namespace subtask1{
bool check(){
return n <= 10;
}
int validate(){
int mx = 0;
FOR(i, 1, numTeams){
maximize(mx, (int) teams[i].size());
for(auto p: teams[i]){
if (teams[i].size() < ord[p].fi) return 0;
}
}
return mx;
}
void backtrack(int pos){
if (pos == n + 1){
int sz = validate();
if (sz) {
if (maximize(bestTeam, numTeams)){
minSize = sz;
FOR(i, 1, bestTeam){
ansTeams[i] = teams[i];
}
}
else if (bestTeam == numTeams and sz < minSize){
minSize = sz;
FOR(i, 1, bestTeam){
ansTeams[i] = teams[i];
}
}
}
return;
}
FOR(i, 1, numTeams){
teams[i].pb(pos);
backtrack(pos + 1);
teams[i].pop_back();
}
++numTeams;
teams[numTeams].pb(pos);
backtrack(pos + 1);
teams[numTeams].pop_back();
--numTeams;
}
void solve(){
backtrack(1);
cout << bestTeam << endl;
// FOR(i, 1, bestTeam){
// cout << ansTeams[i].size() << ' ';
// for(auto p: ansTeams[i]){
// cout << ord[p].se << ' ';
// }
// cout << endl;
// }
}
}
namespace subtask2{
bool check(){
return n <= 5000;
}
void traced(int i){
int type = trace[i].se;
if (type == 1){
++numTeams;
FOR(j, trace[i].fi + 1, i){
teams[numTeams].pb(ord[j].se);
}
}
if (trace[i].fi == 0){
return;
}
traced(trace[i].fi);
}
bool update(ii &a, ii b){
if (a.fi < b.fi){
a = b;
return true;
}
else if (a.fi == b.fi and a.se > b.se) {
a = b;
return true;
}
return false;
}
void solve(){
sort(ord + 1, ord + 1 + n);
FOR(i, 1, n){
FORD(j, i - ord[i].fi, 0){
if (update(dp[i], ii(dp[j].fi + 1, max(dp[j].se, i - j) ))) {
trace[i] = {j, 1};
}
}
}
if (dp[n].fi == 0) {
cout << -1 << endl;
return;
}
cout << dp[n].fi << endl;
traced(n);
FOR(i, 1, dp[n].fi){
cout << teams[i].size() << ' ';
for(auto x: teams[i]){
cout << x << ' ';
}
cout << endl;
}
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n;
FOR(i, 1, n){
cin >> ord[i].fi;
ord[i].se = i;
}
if (subtask2::check()) return subtask2::solve(), 0;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
Compilation message
tea.cpp: In function 'long long int subtask1::validate()':
tea.cpp:46:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
46 | if (teams[i].size() < ord[p].fi) return 0;
| ^
tea.cpp: At global scope:
tea.cpp:155:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
155 | main()
| ^~~~
tea.cpp: In function 'int main()':
tea.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19024 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
19024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19024 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19024 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
21072 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
21156 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
23120 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
