Submission #1108770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108770		Pacybwoah	Table Tennis (JOI24_tabletennis)	C++17	100 / 100	968 ms	111432 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2")
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        ll n, m;
        cin >> n >> m;
        m = n * (n - 1) * (n - 2) / 6 - m;
        auto c2 = [&](ll a){
            return a * (a - 1) / 2;
        };
        vector<ll> deg(n + 1, -1);
        ll cur = 0, tar = c2(n), cur2 = 0;
        bool flag = 1;
        for(int i = 1; i < n; i++){
            for(ll j = 0; j < n; j++){
                if(cur + j < c2(i)) continue;
                ll rest = tar - cur - j, rm = m - cur2 - c2(j), rn = n - i;
                ll mini = c2(rest / rn) * (rn - (rest % rn)) + c2(rest / rn + 1) * (rest % rn);
                if(mini > rm) continue;
                deg[i] = j;
                cur += j;
                cur2 += c2(j);
                break;
            }
            if(deg[i] == -1){
                flag = 0;
                break;
            }
        }
        deg[n] = tar - cur;
        if(cur2 + c2(deg[n]) != m || deg[n] >= n || deg[n] < 0) flag = 0;
        //for(int i = 1; i <= n; i++) cout << deg[i] << "\n";
        if(flag){
            cout << "Yes\n";
            sort(next(deg.begin()), deg.end());
            vector<vector<int>> ans(n + 1, vector<int>(n + 1));
            vector<pair<int, int>> degs;
            for(int i = 1; i <= n; i++) degs.emplace_back(deg[i], i);
            for(int i = n; i > 0; i--){
                sort(degs.begin(), degs.end());
                auto [val, id] = degs.back();
                degs.pop_back();
                for(int j = 0; j < (int)degs.size(); j++){
                    auto &[val2, id2] = degs[j];
                    if(j < val) ans[id][id2] = 1;
                    else{
                        ans[id2][id] = 1;
                        val2--;
                    }
                }
            }
            ll sum = 0;
            for(int i = 2; i <= n; i++){
                for(int j = 1; j < i; j++) cout << ans[i][j];
                cout << "\n";
            }
        }
        else cout << "No\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:63:16: warning: unused variable 'sum' [-Wunused-variable]
   63 |             ll sum = 0;
      |                ^~~

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