Submission #1114890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114890		salmon	Table Tennis (JOI24_tabletennis)	C++14	4 / 100	716 ms	113604 KiB

Main

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

int t;
long long int N;
long long int M;
int adjmat[5100][5100];
int nom[5100];
int last[5100];
queue<pair<int,pair<int,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;
            }
        }

        for(int i = 0; i < N + 6; i++){
            nom[i] = 0;
        }

        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;

            nom[h1]++;
            if(nom[h1] % 2 == 0) q.push({h1,{i,last[h1]}});
            last[h1] = i;
        }

        while(num != 0){
            if(q.empty()) printf("onojon");
            pair<int,pair<int,int>> iii = q.front();
            q.pop();

            int h = iii.first;

            int n1 = iii.second.first;
            int n2 = iii.second.second;

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

            nom[h + b]++;
            if(nom[h + b] % 2 == 0) q.push({h + b,{n1,last[h + b]}});
            last[h + b] = n1;

            nom[h - b]++;
            if(nom[h - b] % 2 == 0) q.push({h - b,{n2,last[h - b]}});
            last[h - b] = n2;

            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:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf(" %d",&t);
      |     ~~~~~^~~~~~~~~~
Main.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf(" %lld",&N);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf(" %lld",&M);
      |         ~~~~~^~~~~~~~~~~~

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