Submission #1111442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111442		Requiem	Teams (CEOI11_tea)	C++17	0 / 100	33 ms	23120 KiB

tea

#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;
const int MAXN = 3e5 + 9;
ii dp[MAXN];
int n;

ii ord[MAXN];
ii trace[MAXN];

int numTeams = 0;

int bestTeam = 0;
int minSize = inf;

vector<int> teams[MAXN];
vector<int> ansTeams[MAXN];

namespace subtask1{
    bool check(){
        return n <= 10;
    }

    int validate(){
        int mx = 0;
        FOR(i, 1, numTeams){
            maximize(mx, (int) teams[i].size());
            for(auto p: teams[i]){
                if (teams[i].size() < ord[p].fi) return 0;
            }
        }
        return mx;
    }
    void backtrack(int pos){
        if (pos == n + 1){
            int sz = validate();

            if (sz) {
                if (maximize(bestTeam, numTeams)){
                    minSize = sz;
                    FOR(i, 1, bestTeam){
                        ansTeams[i] = teams[i];
                    }
                }
                else if (bestTeam == numTeams and sz < minSize){
                    minSize = sz;
                    FOR(i, 1, bestTeam){
                        ansTeams[i] = teams[i];
                    }
                }
            }
            return;
        }

        FOR(i, 1, numTeams){
            teams[i].pb(pos);
            backtrack(pos + 1);
            teams[i].pop_back();
        }
        ++numTeams;
        teams[numTeams].pb(pos);
        backtrack(pos + 1);
        teams[numTeams].pop_back();
        --numTeams;
    }
    void solve(){
        backtrack(1);
        cout << bestTeam << endl;
//        FOR(i, 1, bestTeam){
//            cout << ansTeams[i].size() << ' ';
//            for(auto p: ansTeams[i]){
//                cout << ord[p].se << ' ';
//            }
//            cout << endl;
//        }

    }
}
namespace subtask2{
    bool check(){
        return n <= 5000;
    }
    void traced(int i){
        int type = trace[i].se;
        if (type == 1){
            ++numTeams;
            FOR(j, trace[i].fi + 1, i){
                teams[numTeams].pb(ord[j].se);
            }
        }

        if (trace[i].fi == 0){
            return;
        }
        traced(trace[i].fi);

    }

    bool update(ii &a, ii b){
        if (a.fi < b.fi){
            a = b;
            return true;
        }
        else if (a.fi == b.fi and a.se > b.se) {
            a = b;
            return true;
        }
        return false;
    }
    void solve(){
        sort(ord + 1, ord + 1 + n);
        FOR(i, 1, n){

            FORD(j, i - ord[i].fi, 0){
                if (update(dp[i], ii(dp[j].fi + 1, max(dp[j].se, i - j) ))) {
                    trace[i] = {j, 1};
                }
            }
        }

        if (dp[n].fi == 0) {
            cout << -1 << endl;
            return;
        }
        cout << dp[n].fi << endl;
        traced(n);
        FOR(i, 1, dp[n].fi){
            cout << teams[i].size() << ' ';
            for(auto x: teams[i]){
                cout << x << ' ';
            }
            cout << endl;
        }

    }
}

main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n;
    FOR(i, 1, n){
        cin >> ord[i].fi;
        ord[i].se = i;
    }

    if (subtask2::check()) return subtask2::solve(), 0;

}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message (stderr)

tea.cpp: In function 'long long int subtask1::validate()':
tea.cpp:46:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   46 |                 if (teams[i].size() < ord[p].fi) return 0;
      |                                     ^
tea.cpp: At global scope:
tea.cpp:155:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  155 | main()
      | ^~~~
tea.cpp: In function 'int main()':
tea.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tea.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10