oj.uz

Submission #321231

# Submission time Handle Problem Language Result Execution time Memory
321231 2020-11-11T15:54:42 Z prasanth30 Collecting Mushrooms (NOI18_collectmushrooms) C++14
79 / 100
 2000 ms 15832 KB 
#include <bits/stdc++.h>
using namespace std;
//actual solution is at bottom//
////<pbds>////
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
    rb_tree_tag, tree_order_statistics_node_update>; 
// change null_type for map
// change less to less_equal for multiset
#define ook order_of_key
#define fbo find_by_order*/
///</pbds>///

#define int long long int
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define google(i) cout<<"Case #"<<i<<" :";
///<constants>///
const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = 4*atan((ld)1); 
const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
///</constants>///

///<IO>/// 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
 
using namespace io;
///</IO>///

///<execution-time>///
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
/*example for clock usage
    clock_t z = clock();
    debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
*/
///</execution-time>///
signed main(){
    setIO("");
    int r,c,d,k;cin>>r>>c>>d>>k;
    vector<pair<int,int>> mush,sprin;
    vector<int> musc,sprinc;
    for(int i=1;i<=r;i++){
    	for(int j=1;j<=c;j++){
    		char c;cin>>c;
    		if(c=='.')continue;
    		if(c=='M'){mush.pb({i,j});musc.pb(j);}
    		if(c=='S'){sprin.pb({i,j});sprinc.pb(j);}
    	}
    }
    int ans=0;
    if(r==1){
    	for(int i=0;i<musc.size();i++){
    		int c=0;
    		auto l=lower_bound(sprinc.begin(), sprinc.end(),max(musc[i]-d,0LL));
    		auto r=upper_bound(sprinc.begin(),sprinc.end(),max(musc[i]+d,0LL));
    		if((int)(r-l)>=k)ans++;
    		//cout<<(r-l)<<"\n";
    	}	
    }
    else{for(int i=0;i<mush.size();i++){
    	int c=0;
    	for(int j=0;j<sprin.size();j++){
    		if(max(abs(sprin[j].first-mush[i].first),abs(sprin[j].second-mush[i].second))<=d)c++;
    		if(c>=k)break;
    	}
    	if(c>=k)ans++;
    }}
    cout<<ans<<"\n";
    return 0;
}
/* stuff you should look for
    * check whether you have read the problem correctly
    * int overflow, array bounds
    * special cases (n=1?), slow multiset operations
    * do smth instead of nothing and stay organized

....M
.M...
..S..
.S...
...M.
*/

Compilation message

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |      for(int i=0;i<musc.size();i++){
      |                  ~^~~~~~~~~~~~
mushrooms.cpp:69:11: warning: unused variable 'c' [-Wunused-variable]
   69 |       int c=0;
      |           ^
mushrooms.cpp:76:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     else{for(int i=0;i<mush.size();i++){
      |                      ~^~~~~~~~~~~~
mushrooms.cpp:78:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |      for(int j=0;j<sprin.size();j++){
      |                  ~^~~~~~~~~~~~~
mushrooms.cpp: In function 'void io::setIn(std::string)':
mushrooms.cpp:34:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp: In function 'void io::setOut(std::string)':
mushrooms.cpp:35:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 18 ms 620 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 9 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #4
23.0 / 23.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8528 KB Output is correct
2 Correct 40 ms 15832 KB Output is correct
3 Correct 38 ms 13264 KB Output is correct
4 Correct 38 ms 13916 KB Output is correct
5 Correct 46 ms 14820 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 18 ms 620 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 9 ms 748 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 4 ms 364 KB Output is correct
17 Correct 4 ms 364 KB Output is correct
18 Correct 4 ms 364 KB Output is correct
19 Correct 4 ms 364 KB Output is correct
20 Correct 4 ms 364 KB Output is correct
21 Correct 28 ms 8528 KB Output is correct
22 Correct 40 ms 15832 KB Output is correct
23 Correct 38 ms 13264 KB Output is correct
24 Correct 38 ms 13916 KB Output is correct
25 Correct 46 ms 14820 KB Output is correct
26 Execution timed out 2085 ms 7632 KB Time limit exceeded
27 Halted 0 ms 0 KB -