oj.uz

답안 #1112314

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112314 2024-11-14T03:55:32 Z Requiem Teams (CEOI11_tea) C++17
100 / 100
 683 ms 111948 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 + 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:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main()
      | ^~~~
tea.cpp: In function 'int main()':
tea.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39760 KB Output is correct
2 Correct 8 ms 39772 KB Output is correct
3 Correct 8 ms 39928 KB Output is correct
4 Correct 7 ms 39876 KB Output is correct
5 Correct 10 ms 39760 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 39760 KB Output is correct
2 Correct 8 ms 39760 KB Output is correct
3 Correct 8 ms 39760 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 39760 KB Output is correct
2 Correct 8 ms 39760 KB Output is correct
3 Correct 11 ms 35664 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 40016 KB Output is correct
2 Correct 15 ms 35408 KB Output is correct
3 Correct 19 ms 33616 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 33788 KB Output is correct
2 Correct 15 ms 35920 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 40152 KB Output is correct
2 Correct 52 ms 46996 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 43848 KB Output is correct
2 Correct 52 ms 46920 KB Output is correct
3 Correct 57 ms 41032 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 487 ms 92232 KB Output is correct
2 Correct 490 ms 92488 KB Output is correct
3 Correct 440 ms 90536 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 106880 KB Output is correct
2 Correct 600 ms 111948 KB Output is correct
3 Correct 683 ms 109128 KB Output is correct
4 Correct 586 ms 104212 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 517 ms 96792 KB Output is correct
2 Correct 179 ms 79792 KB Output is correct
3 Correct 617 ms 109132 KB Output is correct
4 Correct 635 ms 108708 KB Output is correct