oj.uz

답안 #1112327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112327 2024-11-14T04:28:46 Z Requiem Teams (CEOI11_tea) C++17
100 / 100
 563 ms 127556 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 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 + 1;

vector<ii> query[MAXN];
vector<int> listPosition[MAXN];
int pos_ptr[MAXN];
int ord[MAXN], cnt[MAXN], newOrd[MAXN];
int n;
int dp[MAXN], trace[MAXN], mx = 0;

void fastscan(int &number){
    //variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    // extract current character from buffer
    c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;

        // extract the next character from the buffer
        c = getchar();
    }

    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;

    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}

int stk[MAXN], sz_stk = 0;

int lab[MAXN];

inline int root(int u){
    return (lab[u] < 0) ? u : lab[u] = root(lab[u]);
}

bool check(int mid){
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;

    memset(lab, -1, sizeof(lab));
    FOR(i, 1, n){
        if (i - ord[i] >= 0) query[i - ord[i]].pb({max(0, i - mid), i});
    }

    sz_stk = 0;
    FOR(i, 0, n){
        if (sz_stk == 0) stk[sz_stk++] = i;
        else{
            while(sz_stk > 0 and dp[stk[ sz_stk - 1 ] ]< dp[i]){
                lab[stk[sz_stk - 1]] = i;
                sz_stk--;
            }
            stk[sz_stk++] = i;

        }
        for(auto &p: query[i]){
            dp[p.se] = dp[root(p.fi)] + 1;
            trace[p.se] = root(p.fi);
        }
    }
    FOR(i, 1, n){
        if (i - ord[i] >= 0) query[i - ord[i]].pop_back();
    }
    return dp[n] == mx;
}

void traced(int s){
    while(true){
        int tr = trace[s];
        cout << s - tr << ' ';
        FOR(i, tr + 1, s){
            cout << listPosition[ord[i]][pos_ptr[ord[i]] - 1] << ' ';
            pos_ptr[ord[i]]--;
        }
        cout << endl;
        if (tr == 0) return;
        s = trace[s];
    }
}

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];

        listPosition[ord[i]].pb(i);
        pos_ptr[ord[i]]++;
        maximize(mxA, ord[i]);

        cnt[ord[i]]++;
    }

    FOR(i, 1, n){
        cnt[i] += cnt[i - 1];
    }

    FOR(i, 1, n){
        newOrd[cnt[ord[i]]--] = ord[i];
    }
    FOR(i, 1, n){
        ord[i] = newOrd[i];
    }

    check(n);
    mx = dp[n];

    int l = mxA, r = n - 1, res = n;
    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: In function 'void fastscan(int&)':
tea.cpp:47:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   47 |     register int c;
      |                  ^
tea.cpp: At global scope:
tea.cpp:126:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  126 | main()
      | ^~~~
tea.cpp: In function 'int main()':
tea.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 66384 KB Output is correct
2 Correct 10 ms 66384 KB Output is correct
3 Correct 12 ms 66384 KB Output is correct
4 Correct 13 ms 66424 KB Output is correct
5 Correct 11 ms 66552 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 66384 KB Output is correct
2 Correct 12 ms 66384 KB Output is correct
3 Correct 13 ms 66552 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 66384 KB Output is correct
2 Correct 15 ms 66384 KB Output is correct
3 Correct 14 ms 64592 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 69044 KB Output is correct
2 Correct 46 ms 69624 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 67824 KB Output is correct
2 Correct 51 ms 69452 KB Output is correct
3 Correct 54 ms 64840 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 106052 KB Output is correct
2 Correct 342 ms 104744 KB Output is correct
3 Correct 325 ms 103272 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 410 ms 115828 KB Output is correct
2 Correct 545 ms 127556 KB Output is correct
3 Correct 461 ms 117452 KB Output is correct
4 Correct 472 ms 112544 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 105200 KB Output is correct
2 Correct 135 ms 85688 KB Output is correct
3 Correct 471 ms 117632 KB Output is correct
4 Correct 563 ms 117576 KB Output is correct