Submission #1034158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034158		Antekb	Table Tennis (JOI24_tabletennis)	C++17	4 / 100	1073 ms	604 KiB

Main

#include "bits/stdc++.h"	/** keep-include */
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

vector<vector<int> > get_tournament(vector<int> V){
    deb(V);
    int n=V.size();
    if(n==1){
        assert(V==vi({0}));
        return {{0}};
    }
    int d=n-1-V.back();
    V.pop_back();
    vi decreased;
    vi cur;
    for(int i=n-2; ; i--){
        if(i!=n-2 && (i==-1 || V[i]!=V[i+1])){
            while(d && cur.size()){
                assert(V[cur.back()]);
                V[cur.back()]--;
                decreased.pb(cur.back());
                cur.pop_back();
                d--;
            }
            cur.clear();
        }
        if(i==-1)break;
        cur.pb(i);
    }
    auto res=get_tournament(V);
    res.pb(vi(n-1, 1));
    for(int i=0; i<n-1; i++){
        res[i].pb(0);
    }
    for(int i:decreased){
        res[i][n-1]=1;
        res[n-1][i]=0;
    }
    return res;
}

vector<int> degrees;

bool backtrack(int n, int sum_deg, int sum_deg2, int max_deg){
    deb(n, sum_deg, sum_deg2, max_deg);
    if(sum_deg<n*(n-1)/2)return false;
    if(n==1){
        if(sum_deg2==sum_deg*sum_deg && sum_deg<=max_deg){
            degrees.pb(sum_deg);
            return 1;
        }
        else return 0;
    }
    for(int deg=max_deg; deg>=0; deg--){
        degrees.pb(deg);
        if(backtrack(n-1, sum_deg-deg, sum_deg2-deg*deg, deg))return true;
        degrees.pop_back();
    }
    return false;
}

//pamietac o tym ze m long longiem gdy n >=2000
void solve() {
	int n, m;
    cin>>n>>m;
    int sum_deg=n*(n-1)/2;
    int sum_deg2=2*(sum_deg*(n-2)/3-m)+sum_deg;
    deb(sum_deg, sum_deg2);
    if(!backtrack(n, sum_deg, sum_deg2, n-1)){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
    reverse(all(degrees));
    auto res=get_tournament(degrees);
    degrees.clear();
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++)cout<<res[i][j];
        cout<<"\n";
    }
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	cin >> tt;
	FOR(te, 0, tt) solve();
	return 0;
}

Compilation message (stderr)

Main.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Main.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Main.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Main.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Main.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 4 / 4
• Subtask 3: 0 / 23
• Subtask 4: 0 / 30
• Subtask 5: 0 / 15
• Subtask 6: 0 / 23