Submission #1112304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112304	2024-11-14T03:33:07 Z	Requiem	Teams (CEOI11_tea)	C++17	100 / 100	1626 ms	106956 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ỉ.
**/

struct dsu{
    vector<int> lab;
    dsu(int sz = 0){
        lab.resize(sz + 9, -1);
    }

    int root(int u){
        return (lab[u] < 0) ? u : lab[u] = root(lab[u]);
    }
};

const int MAXN = 1e6 + 1;

vector<ii> query[MAXN];
ii ord[MAXN];
int n;
int dp[MAXN], trace[MAXN], mx = 0;

bool check(int mid){
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;

    dsu D(n);
    FOR(i, 1, n){
        if (i - ord[i].fi >= 0) query[i - ord[i].fi].pb({max(0LL, i - mid), i});
    }
    vector<int> stk;
    FOR(i, 0, n){
        if (stk.empty()) stk.pb(i);
        else{
            while(stk.size() > 0 and dp[stk.back()] < dp[i]){
                D.lab[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[D.root(l)] + 1;
            trace[id] = D.root(l);
        }
    }

    FOR(i, 0,n){
        query[i].clear();
        query[i].shrink_to_fit();
    }
    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:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main()
      | ^~~~
tea.cpp: In function 'int main()':
tea.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	34384 KB	Output is correct
2	Correct	8 ms	34384 KB	Output is correct
3	Correct	12 ms	33016 KB	Output is correct
4	Correct	13 ms	32080 KB	Output is correct
5	Correct	14 ms	31988 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	32080 KB	Output is correct
2	Correct	15 ms	32080 KB	Output is correct
3	Correct	17 ms	32144 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	32336 KB	Output is correct
2	Correct	21 ms	32336 KB	Output is correct
3	Correct	22 ms	32336 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	32336 KB	Output is correct
2	Correct	26 ms	32468 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	37640 KB	Output is correct
2	Correct	95 ms	37844 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	38436 KB	Output is correct
2	Correct	94 ms	37372 KB	Output is correct
3	Correct	112 ms	38436 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	980 ms	87644 KB	Output is correct
2	Correct	998 ms	86632 KB	Output is correct
3	Correct	961 ms	89192 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1191 ms	105572 KB	Output is correct
2	Correct	1626 ms	104228 KB	Output is correct
3	Correct	1198 ms	104332 KB	Output is correct
4	Correct	1089 ms	97916 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	915 ms	98400 KB	Output is correct
2	Correct	229 ms	78996 KB	Output is correct
3	Correct	1233 ms	105152 KB	Output is correct
4	Correct	1410 ms	106956 KB	Output is correct