oj.uz

Submission #1112312

# Submission time Handle Problem Language Result Execution time Memory
1112312 2024-11-14T03:51:18 Z Requiem Teams (CEOI11_tea) C++17
100 / 100
 623 ms 111932 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;
vector<int> stk;

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});
    }

    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]){
                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, 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: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 7 ms 34384 KB Output is correct
2 Correct 7 ms 34384 KB Output is correct
3 Correct 7 ms 34384 KB Output is correct
4 Correct 6 ms 34384 KB Output is correct
5 Correct 7 ms 34384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 34732 KB Output is correct
2 Correct 9 ms 34384 KB Output is correct
3 Correct 7 ms 34524 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 34384 KB Output is correct
2 Correct 8 ms 34416 KB Output is correct
3 Correct 8 ms 34400 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 34640 KB Output is correct
2 Correct 11 ms 34768 KB Output is correct
3 Correct 15 ms 34800 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34640 KB Output is correct
2 Correct 10 ms 34640 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41900 KB Output is correct
2 Correct 49 ms 42196 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 42376 KB Output is correct
2 Correct 47 ms 42244 KB Output is correct
3 Correct 50 ms 42544 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 87148 KB Output is correct
2 Correct 455 ms 87388 KB Output is correct
3 Correct 420 ms 85380 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 98852 KB Output is correct
2 Correct 623 ms 111932 KB Output is correct
3 Correct 605 ms 101400 KB Output is correct
4 Correct 526 ms 95388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 87828 KB Output is correct
2 Correct 159 ms 71452 KB Output is correct
3 Correct 549 ms 101296 KB Output is correct
4 Correct 589 ms 100748 KB Output is correct