Submission #1162341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162341		tosivanmak	Table Tennis (JOI24_tabletennis)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int f(int n) {
    int res = 0, h = n / 2;
    // h, n-1-h
    for (int i = 1; i <= n; i++) {
        res += h * (h - 1) / 2;
        res += (n - h - 2) * (n - h - 1) / 2;
    }
    // cout << "res " << n << " " << res << '\n';
    return n * (n - 1) * (n - 2) / 6 - (res / 2);
}

vector<vector<int>> comp(int n, int x) {
    vector<vector<int>> g(n+1, vector<int> (n+1, -1));
    auto norm = [&] (int i) {
        if (i > n) return i - n;
        return i;  
    };
    auto ae = [&] (int a, int b) {
        if (a < b) g[b][a] = 1;
        else g[a][b] = 0;
    };
    vector<int> d(n+1, 0);
    vector<set<int>> val(n+1);
    set<int> cand;
    for (int i = 1; i <= n; i++) {
        int t = n/2, x = norm(i+1);
        if (n % 2 == 0 && i > n/2) t--;
        while (t--) {
            ae(i, x);
            d[x]++;
            x = norm(x+1);
        }
    }
    for (int i = 1; i <= n; i++) val[d[i]].insert(i);
    for (int i = 1; i <= n; i++) if (val[i].size() >= 2) cand.insert(i);
    int times = f(n) - x;
    for (int i = 0; i < times; i++) {
        // cout << times << ' ' << i << '\n';
        assert(!cand.empty());
        int tp = *cand.begin();
        cand.erase(tp);
        assert(val[tp].size() >= 2);
        int f = *val[tp].begin(); val[tp].erase(f);
        int s = *val[tp].begin(); val[tp].erase(s);
        if (g[f][s]) d[f]--, d[s]++;
        else d[f]++, d[s]--;
        g[f][s] ^= 1;
        val[d[f]].insert(f);
        val[d[s]].insert(s);
        cand.erase(f); cand.erase(s);
        if (val[d[f]].size() >= 2) cand.insert(d[f]);
        if (val[d[s]].size() >= 2) cand.insert(d[s]);
        if (val[tp].size() >= 2) cand.insert(tp);
    }
    // for (int i = 2; i <= n; i++) {
    //     for (int j = 1; j < i; j++) cout << g[i][j];
    //     cout << '\n';
    // }
    return g;
}

void solve() {
    int n, m, np = -1;
    cin >> n >> m;
    for (int i = 1;; i++) {
        // cout << i << " " << f(i) << "\n";
        if (f(i) >= m) {
            np = i;
            break;
        }
    }
    if (np > n || np == -1) return cout << "No\n", void();
    vector<vector<int>> g = comp(np, m);
    // 1 <=> larger wins
    cout << "Yes\n";
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (i > np || j > np) g[i][j] = 1;
            cout << g[i][j];
        }
        cout << '\n';
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> q;
    while (q--) solve();
}

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