oj.uz

Submission #404351

# Submission time Handle Problem Language Result Execution time Memory
404351 2021-05-14T08:58:09 Z Ruxandra985 Red-blue table (IZhO19_stones) C++14
100 / 100
 52 ms 2200 KB 
#include <bits/stdc++.h>

using namespace std;
char a[1010][1010];
int f[1010] , ok[1010];
priority_queue <pair <int , int> > h;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int t , n , m , i , j , opt , sol , val , poz;
    fscanf (fin,"%d",&t);
    //t = 16;
    //n = 1;
    //m = 0;
    for (;t;t--){

        fscanf (fin,"%d%d",&n,&m);
        //m++;
        //if (m > 4){
          //  m = 1;
           // n++;
        //}

        if (n >= m){

            for (i = 1 ; i <= n ; i++){
                for (j = 1 ; j <= m ; j++){
                    a[i][j] = '+';
                }
            }
            opt = m - (m / 2 + 1);
            sol = n;

            for (i = 1 ; i <= n ; i++){
                h.push(make_pair(0 , i));
                f[i] = 0;
            }

            for (i = 1 ; i <= m ; i++){

                /// poti sa scoti n / 2 + 1 elem din h a.i toate < opt??

                for (j = 1 ; j <= n / 2 + 1 ; j++){

                    val = -h.top().first;
                    poz = h.top().second;
                    h.pop();

                    if (val + 1 <= opt){
                        ok[j] = poz;
                    }
                    else break;

                }

                if (j > n / 2 + 1){ /// se poate

                    sol++;

                    for (j = 1 ; j <= n / 2 + 1 ; j++){
                        f[ok[j]]++;
                        h.push(make_pair(-f[ok[j]] , ok[j]));
                        a[ok[j]][i] = '-';
                    }

                }


            }


            fprintf (fout,"%d\n" , sol);
            for (i = 1 ; i <= n ; i++){
                for (j = 1 ; j <= m ; j++){
                    fputc(a[i][j] , fout);
                }
                fprintf (fout,"\n");
            }

            while (!h.empty())
                h.pop();

        }
        else {

            for (i = 1 ; i <= n ; i++){
                for (j = 1 ; j <= m ; j++){
                    a[i][j] = '-';
                }
            }

            opt = n - (n / 2 + 1);
            sol = m;

            for (i = 1 ; i <= m ; i++){
                h.push(make_pair(0 , i));
                f[i] = 0;
            }

            for (i = 1 ; i <= n ; i++){

                /// poti sa scoti m / 2 + 1 elem din h a.i toate < opt??

                for (j = 1 ; j <= m / 2 + 1 ; j++){

                    val = -h.top().first;
                    poz = h.top().second;
                    h.pop();

                    if (val + 1 <= opt){
                        ok[j] = poz;
                    }
                    else break;

                }

                if (j > m / 2 + 1){ /// se poate

                    sol++;

                    for (j = 1 ; j <= m / 2 + 1 ; j++){
                        f[ok[j]]++;
                        h.push(make_pair(-f[ok[j]] , ok[j]));
                        a[i][ok[j]] = '+';
                    }

                }


            }


            fprintf (fout,"%d\n" , sol);
            for (i = 1 ; i <= n ; i++){
                for (j = 1 ; j <= m ; j++){
                    fputc(a[i][j] , fout);
                }
                fprintf (fout,"\n");
            }
            while (!h.empty())
                h.pop();

        }



    }
    return 0;
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:12:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     fscanf (fin,"%d",&t);
      |     ~~~~~~~^~~~~~~~~~~~~
stones.cpp:18:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         fscanf (fin,"%d%d",&n,&m);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1388 KB Output is correct
2 Correct 44 ms 1948 KB Output is correct
3 Correct 44 ms 2000 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1360 KB Output is correct
2 Correct 46 ms 1772 KB Output is correct
3 Correct 35 ms 1612 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 40 ms 1388 KB Output is correct
6 Correct 44 ms 1948 KB Output is correct
7 Correct 44 ms 2000 KB Output is correct
8 Correct 44 ms 1360 KB Output is correct
9 Correct 46 ms 1772 KB Output is correct
10 Correct 35 ms 1612 KB Output is correct
11 Correct 9 ms 564 KB Output is correct
12 Correct 39 ms 1864 KB Output is correct
13 Correct 40 ms 2024 KB Output is correct
14 Correct 29 ms 1644 KB Output is correct
15 Correct 52 ms 2200 KB Output is correct
16 Correct 36 ms 1744 KB Output is correct
17 Correct 16 ms 1228 KB Output is correct