Submission #1112327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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