Submission #1112315

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112315	2024-11-14T03:56:44 Z	Requiem	Teams (CEOI11_tea)	C++17	100 / 100	597 ms	111944 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"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
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 + 10;


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 s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        int tr = trace[x];
        cout << x - tr << ' ';
        FOR(i, tr + 1, x){
            cout << ord[i].se << ' ';
        }
        cout << endl;
        if (tr != 0) q.push(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:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main()
      | ^~~~
tea.cpp: In function 'int main()':
tea.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	39760 KB	Output is correct
2	Correct	8 ms	39908 KB	Output is correct
3	Correct	8 ms	39908 KB	Output is correct
4	Correct	7 ms	39760 KB	Output is correct
5	Correct	8 ms	39760 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	39760 KB	Output is correct
2	Correct	7 ms	39760 KB	Output is correct
3	Correct	9 ms	39776 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	39928 KB	Output is correct
2	Correct	7 ms	39904 KB	Output is correct
3	Correct	8 ms	39760 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	35920 KB	Output is correct
2	Correct	13 ms	40016 KB	Output is correct
3	Correct	10 ms	40016 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	40016 KB	Output is correct
2	Correct	11 ms	40176 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	45264 KB	Output is correct
2	Correct	43 ms	47096 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	41032 KB	Output is correct
2	Correct	47 ms	40244 KB	Output is correct
3	Correct	48 ms	45896 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	413 ms	91500 KB	Output is correct
2	Correct	447 ms	93768 KB	Output is correct
3	Correct	368 ms	92352 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	506 ms	106684 KB	Output is correct
2	Correct	490 ms	111944 KB	Output is correct
3	Correct	597 ms	109132 KB	Output is correct
4	Correct	484 ms	102084 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	450 ms	95980 KB	Output is correct
2	Correct	187 ms	78696 KB	Output is correct
3	Correct	546 ms	109108 KB	Output is correct
4	Correct	535 ms	108488 KB	Output is correct