oj.uz

Submission #919561

# Submission time Handle Problem Language Result Execution time Memory
919561 2024-02-01T06:48:37 Z manizare Red-blue table (IZhO19_stones) C++14
100 / 100
 50 ms 3512 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ; 
using namespace std ;   
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6+ 10 , maxm = 1e6+10 , lg = 18 , inf= 1e18 , mod = 998244353 ;
int t[maxn] ;char A[maxn] ;

int f(int a ,int n){
    return max(0ll , (n+2)/2 - (n-a));
}

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
    int T ;
    cin >>  T ;
    while(T--){
        int n , m ;
        cin >> n >> m ;
        int mx = -1 , a , b ;
        rep(i , 0 , n){
            int l =0 , r = m+1 ;
            while(r-l>1){
                int mid = (l+r)/2 ;
                if(f(mid , m)*i+f(i , n)*mid > i*mid){
                    r = mid ;
                }else{
                    l = mid ;
                }
            }
            if(mx < l+i){
                a = i ;
                b = l ;
                mx = l+i ;
            }
        }
        cout << mx << "\n";
        rep(i , 1, b){
            t[i] = f(a , n) ;
        } 
        rep(i , 1 ,a){
            vector <pii> vec;
            rep(i , 1 , b){
                vec.pb({t[i] ,i}) ;
                A[i] = '+' ;
            }
            sort(all(vec)) ;
            int x = b-f(b , m) ;
            while(x--){
                A[vec.back().S] = '-' ;
                t[vec.back().S]--;
                vec.pop_back() ;
            }
            rep(i , 1 ,b){
                cout << A[i] ;
            }
            rep(i , b+1 ,m ){
                cout << "+";
            }
            cout << "\n"; 
        }
        rep(i , a+1 , n){
            rep(j ,1 , m){
                cout << "-";
            }
            cout << "\n"; 
        }
    }
}
/*
    
*/

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:59:30: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             int x = b-f(b , m) ;
      |                              ^
stones.cpp:12:38: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 | #define rep(i , a , b) for(int i=a;i <= (b);i++)
      |                                      ^~
stones.cpp:31:23: note: 'a' was declared here
   31 |         int mx = -1 , a , b ;
      |                       ^

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3512 KB Output is correct
2 Correct 44 ms 3408 KB Output is correct
3 Correct 35 ms 3160 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3408 KB Output is correct
2 Correct 40 ms 3316 KB Output is correct
3 Correct 37 ms 3152 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 40 ms 3512 KB Output is correct
6 Correct 44 ms 3408 KB Output is correct
7 Correct 35 ms 3160 KB Output is correct
8 Correct 42 ms 3408 KB Output is correct
9 Correct 40 ms 3316 KB Output is correct
10 Correct 37 ms 3152 KB Output is correct
11 Correct 9 ms 2648 KB Output is correct
12 Correct 31 ms 3160 KB Output is correct
13 Correct 35 ms 3272 KB Output is correct
14 Correct 29 ms 3024 KB Output is correct
15 Correct 50 ms 3444 KB Output is correct
16 Correct 36 ms 3228 KB Output is correct
17 Correct 13 ms 2648 KB Output is correct