oj.uz

답안 #1112315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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