| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1112310 |
2024-11-14T03:49:08 Z |
Requiem |
Teams (CEOI11_tea) |
C++17 |
|
645 ms |
112132 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;
/**
Ta có thể dễ dàng tính được số team nhiều nhất bằng dp thông thường.
Bây giờ ta cần kiểm soát kích thước của tập lớn nhất.
Giả sử tập lớn nhất là mid.
dp_i = dp_j + 1 (j thuộc [i - mid, i - a[i] ].
Ta nhận thấy rằng là i - mid sẽ tăng dần, trong khi i - a[j] sẽ giảm dần.
Mình có thể dùng deque ko nhỉ.
**/
const int MAXN = 1e6 + 1;
vector<ii> query[MAXN];
ii ord[MAXN];
int n;
int dp[MAXN], trace[MAXN], mx = 0;
int lab[MAXN], realLeader[MAXN];
int root(int u){
if (lab[u] < 0) return u;
else return lab[u] = root(lab[u]);
}
void unite(int u, int v){
u = root(u);
v = root(v);
if (u != v){
int newLeader = realLeader[v];
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
realLeader[u] = newLeader;
}
}
int get(int id){
int x = root(id);
return realLeader[x];
}
vector<int> stk;
bool check(int mid){
memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;
FOR(i, 0, n){
realLeader[i] = i;
lab[i] = -1;
}
FOR(i, 1, n){
if (i - ord[i].fi >= 0) query[i - ord[i].fi].pb({max(0LL, i - mid), i});
}
while(!stk.empty()) stk.pop_back();
FOR(i, 0, n){
if (stk.empty()) stk.pb(i);
else{
while(stk.size() > 0 and dp[stk.back()] < dp[i]){
unite(stk.back(), i);
stk.pop_back();
}
stk.pb(i);
}
for(auto p: query[i]){
int l = p.fi;
int id = p.se;
// cout << l << ' ' << i << ' ' << id << ' ' << ' ' << D.root(l) << endl;
dp[id] = dp[get(l)] + 1;
trace[id] = get(l);
}
}
FOR(i, 1, n){
if (i - ord[i].fi >= 0) query[i - ord[i].fi].pop_back();
}
return dp[n] == mx;
}
void traced(int x){
int tr = trace[x];
cout << x - tr << ' ';
FOR(i, tr + 1, x){
cout << ord[i].se << ' ';
}
cout << endl;
if (tr != 0) traced(tr);
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n;
int mxA = 0;
FOR(i, 1, n){
cin >> ord[i].fi;
ord[i].se = i;
maximize(mxA, ord[i].fi);
}
sort(ord + 1, ord + 1 + n);
check(n + 1);
mx = dp[n];
int l = mxA, r = n, res = -1;
while(l <= r){
int mid = (l + r) >> 1;
if (check(mid)){
res = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
check(res);
cout << mx << endl;
traced(n);
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
Compilation message
tea.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
115 | main()
| ^~~~
tea.cpp: In function 'int main()':
tea.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
39760 KB |
Output is correct |
| 2 |
Correct |
8 ms |
39760 KB |
Output is correct |
| 3 |
Correct |
8 ms |
39760 KB |
Output is correct |
| 4 |
Correct |
7 ms |
39944 KB |
Output is correct |
| 5 |
Correct |
7 ms |
39760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
39760 KB |
Output is correct |
| 2 |
Correct |
8 ms |
39924 KB |
Output is correct |
| 3 |
Correct |
8 ms |
39760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
39892 KB |
Output is correct |
| 2 |
Correct |
8 ms |
39760 KB |
Output is correct |
| 3 |
Correct |
9 ms |
35664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
35920 KB |
Output is correct |
| 2 |
Correct |
15 ms |
35412 KB |
Output is correct |
| 3 |
Correct |
16 ms |
33616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
35920 KB |
Output is correct |
| 2 |
Correct |
11 ms |
40016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
39536 KB |
Output is correct |
| 2 |
Correct |
56 ms |
40508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
44124 KB |
Output is correct |
| 2 |
Correct |
50 ms |
42056 KB |
Output is correct |
| 3 |
Correct |
63 ms |
42488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
481 ms |
92220 KB |
Output is correct |
| 2 |
Correct |
540 ms |
92744 KB |
Output is correct |
| 3 |
Correct |
438 ms |
92608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
585 ms |
107196 KB |
Output is correct |
| 2 |
Correct |
568 ms |
112132 KB |
Output is correct |
| 3 |
Correct |
637 ms |
109060 KB |
Output is correct |
| 4 |
Correct |
593 ms |
103108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
529 ms |
95660 KB |
Output is correct |
| 2 |
Correct |
192 ms |
78504 KB |
Output is correct |
| 3 |
Correct |
635 ms |
109128 KB |
Output is correct |
| 4 |
Correct |
645 ms |
108716 KB |
Output is correct |
