Submission #1034344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034344		Antekb	Table Tennis (JOI24_tabletennis)	C++98	77 / 100	1049 ms	422356 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
#define int long long
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


void get_tournament(vector<int> V, vector<vi> &res){
    deb(V);
    int n=V.size();
    if(n==1){
        assert(V==vi({ll(0)}));
        res={{ll(0)}};
        return;
    }
    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);
    }
    get_tournament(V, res);
    assert(res.size()==n-1);
    res.pb(vi(n-1, ll(1)));
    for(int i=0; i<=n-1; i++){
        res[i].pb(0);
    }
    deb(n, decreased);
    for(int i:decreased){
        res[i][n-1]=1;
        res[n-1][i]=0;
    }
}

int degree[5005];
vector<int> degrees;

using lll=__int128;
unordered_set<lll > S;
lll base=6000;
lll base2=base*base*base;
lll base3=base2*base*base;
lll hasz(int a, int b, int c, int d){
    return a+base*b+base2*c+base3*d;
}

bool backtrack(int n, int sum_deg, int sum_deg2, int max_deg){
    deb(n, sum_deg, sum_deg2, max_deg);
    if(sum_deg2<(sum_deg*sum_deg)/n)return false;
    lll hash=hasz(n, sum_deg, sum_deg2, max_deg);
    if(S.find(hash)!=S.end())return false;
    if(n==1){
        if(sum_deg2==sum_deg*sum_deg && sum_deg<=max_deg){
            degree[1]=sum_deg;
            return 1;
        }
        else return 0;
    }
    for(int deg=min(max_deg, sum_deg-(n-2)*(n-1)/2); deg>=0; deg--){
        if(deg*n<sum_deg)break;
        if(sum_deg2>n*deg*deg)break;
        degree[n]=deg;
        if(backtrack(n-1, sum_deg-deg, sum_deg2-deg*deg, deg))return true;
        //degrees.pop_back();
    }
    S.insert(hash);
    return false;
}

//pamietac o tym ze m long longiem gdy n >=2000
void solve(int n, int 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);
    int min_suma=0;
    for(int i=0; i<n; i++){
        int deg=(sum_deg+i)/n;
        min_suma+=deg*deg;
    }
    if(sum_deg2<min_suma || !backtrack(n, sum_deg, sum_deg2, n-1)){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
    degrees=vi(degree+1, degree+n+1);
    for(int i=1; i<=n; i++){
        cerr<<degree[i]<<" ";
    }
    cerr<<endl;
    vector<vi> res;
    get_tournament(degrees, res);
    degrees.clear();
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++)cout<<res[i][j];
        cout<<"\n";
    }
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	bool test=0;
    if(test==0){
        cin >> tt;
        FOR(te, 0, tt){
            int n, m;
            cin>>n>>m;
            solve(n, m);
        }
    }
    else{
        for(int n=3; n<=20; n++){
            int troj=n*(n-1)*(n-2)/6;
            for(int m=0; m<=troj; m++){
                cerr<<n<<" "<<m<<"\n";
                solve(n, m);
            }
        }
    }
    
    return 0;
}

Compilation message (stderr)

Main.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Main.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Main.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Main.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Main.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'void get_tournament(std::vector<long long int>, std::vector<std::vector<long long int> >&)':
Main.cpp:58:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |     assert(res.size()==n-1);
      |            ~~~~~~~~~~^~~~~

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