Submission #1114894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114894		salmon	Table Tennis (JOI24_tabletennis)	C++14	77 / 100	1076 ms	113736 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

int t;
long long int N;
long long int M;
int adjmat[5100][5100];
vector<int> cont[5100];
queue<int> q;

int main(){

    scanf(" %d",&t);

    while(t--){
        scanf(" %lld",&N);
        scanf(" %lld",&M);

        long long int num = N * (N - 1) * (N - 2) / 6 - M;

        if(N % 2 == 1){
            if(num < (N - 1) * (N - 3) / 8 * N ){
                printf("No\n");
                continue;
            }
        }
        else{
            if(num < (N - 2) * (N - 2) * N / 8 ){
                printf("No\n");
                continue;
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(i == j) continue;
            }
        }

        int n = N - 1;
        while(n >= 1){
            if(n % 2 == 1){
                if(num - n * (n - 1) / 2 >= (n - 1) * (n - 3) / 8 * n ){
                    num -= n * (n - 1) / 2;
                }
                else{
                    break;
                }
            }
            else{
                if(num - n * (n - 1) / 2 >= (n - 2) * (n - 2) * n / 8 ){
                    num -= n * (n - 1)/2;
                }
                else{
                    break;
                }
            }

            for(int i = 0; i < n; i++){
                adjmat[n][i] = 1;
                adjmat[i][n] = 0;
            }

            n--;
        }
        n++;

        if(n % 2 == 1){
            for(int i = n; i > 1; i-=2){
                int n1 = i - 1;
                int n2 = i - 2;

                for(int j = 0; j < i/2; j++){
                    adjmat[n1][j] = 0;
                    adjmat[j][n1] = 1;
                }

                for(int j = i/2; j < i - 1; j++){
                    adjmat[n1][j] = 1;
                    adjmat[j][n1] = 0;
                }

                for(int j = 0; j < i/2; j++){
                    adjmat[n2][j] = 1;
                    adjmat[j][n2] = 0;
                }

                for(int j = i/2; j < i - 2; j++){
                    adjmat[n2][j] = 0;
                    adjmat[j][n2] = 1;
                }
            }
        }
        else{
            for(int i = n - 1; i > 1; i-=2){
                int n1 = i - 1;
                int n2 = i - 2;

                for(int j = 0; j < i/2; j++){
                    adjmat[n1][j] = 0;
                    adjmat[j][n1] = 1;
                }

                for(int j = i/2; j < i - 1; j++){
                    adjmat[n1][j] = 1;
                    adjmat[j][n1] = 0;
                }

                for(int j = 0; j < i/2; j++){
                    adjmat[n2][j] = 1;
                    adjmat[j][n2] = 0;
                }

                for(int j = i/2; j < i - 2; j++){
                    adjmat[n2][j] = 0;
                    adjmat[j][n2] = 1;
                }
            }

            int n1 = n - 1;

            for(int j = 0; j < n/2; j++){
                adjmat[n1][j] = 0;
                adjmat[j][n1] = 1;
            }

            for(int j = n/2; j < n - 1; j++){
                adjmat[n1][j] = 1;
                adjmat[j][n1] = 0;
            }
        }

        while(!q.empty()) q.pop();
        for(int i = 0; i < N + 6; i++){
            cont[i].clear();
        }

        for(int i = 0; i < n; i++){
            int h1 = 0;

            for(int j = 0; j < N; j++){
                if(j == i) continue;
                h1 += adjmat[i][j];
            }

            num -= h1 * (h1 - 1)/ 2;

            cont[h1].push_back(i);
            if(cont[h1].size() % 2 == 0) q.push(h1);
        }

        while(num != 0){
            if(q.empty()) printf("onojon");
            int h = q.front();
            q.pop();

            int n1 = cont[h].back();
            cont[h].pop_back();
            int n2 = cont[h].back();
            cont[h].pop_back();

            int b = 1 - 2 * adjmat[n1][n2];

            cont[h + b].push_back(n1);
            if(cont[h + b].size() % 2 == 0) q.push(h + b);

            cont[h - b].push_back(n2);
            if(cont[h - b].size() % 2 == 0) q.push(h - b);

            swap(adjmat[n1][n2],adjmat[n2][n1]);

            num--;
        }

        printf("Yes\n");
        for(int i = 1; i < N; i++){
            for(int j = 0; j < i; j++){
                printf("%d",adjmat[i][j]);
            }
            printf("\n");
        }
    }



}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf(" %d",&t);
      |     ~~~~~^~~~~~~~~~
Main.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf(" %lld",&N);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf(" %lld",&M);
      |         ~~~~~^~~~~~~~~~~~

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