oj.uz

답안 #1112304

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

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

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

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

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

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

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

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

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

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

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