QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87830#5112. Where Am I?zokerWA 2ms3548kbC++174.0kb2023-03-14 14:54:572023-03-14 14:54:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 14:54:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3548kb
  • [2023-03-14 14:54:57]
  • 提交

answer

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

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}



const int N = 1e2+3, K = 26;
//====================================================================//

vector<int> L(1, -1), R(1, -1), cnt(1, 0);
string grid[N];
int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
void testcase(){
	int n, m;
	cin >> m >> n;
	int tot = 0;
	for(int i = 0; i < n; i++)cin >> grid[i], tot += count(grid[i].begin(), grid[i].end(), 'X');
	vector<pair<vector<int>, int>> all;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			all.eb();
			all.back().se = i * m + j;
			int curI = i, curJ = j;
			int k = 1, l = 2, p = 0, t = 0, mov = 0;
			if(grid[i][j] == 'X')all.back().fi.eb(0);
			while(all.back().fi.size() < tot){
				curI += di[p];
				curJ += dj[p];
				mov++;
				if(curI >= 0 && curI < n && curJ >= 0 && curJ < m && grid[curI][curJ] == 'X')all.back().fi.eb(mov);
				t++;
				if(t == k){
					l--;
					t = 0;
					p = (p + 1) & 3;
					if(l == 0)l = 2, k++;
				}
				//dbg(i, j);
			}
		}
	}
	sort(all.begin(), all.end());
	vector<int> ans(all.size());
	auto solve = [&](auto &&solve, int mov, int l, int r, int ind){
		if(l == r){
			ans[l] = mov - 1;
			return;
		}
		int lo = l, hi = r + 1;
		while(lo < hi){
			int mid = lo + hi >> 1;
			if(all[mid].fi[ind] == mov)lo = mid + 1;
			else hi = mid;
		}
		if(l != lo)solve(solve, mov + 1, l, lo - 1, ind + 1);
		if(lo != r + 1)solve(solve, mov + 1, lo, r, ind);
	};
	
	solve(solve, 0, 0, all.size() - 1, 0);
	
	ld sum = accumulate(ans.begin(), ans.end(), 0LL);
	sum /= ans.size();
	cout << fixed << setprecision(10) << sum << "\n";
	int mx = *max_element(ans.begin(), ans.end());
	cout << mx << "\n";
	vii temp;
	for(int i = 0; i < ans.size(); i++){
		if(ans[i] == mx){
			temp.eb(n - all[i].se / m, all[i].se % m + 1);
		}
	}
	sort(temp.begin(), temp.end());
	for(int i = 0; i < temp.size(); i++){
		cout << "(" << temp[i].se << ", " << temp[i].fi << ")" << " \n"[i + 1 == temp.size() ];
	}
	cout << "\n";
	
}





int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int T = 1;
	//cin >> T;
	
	for(int qq = 1; qq <= T; ++qq){
		//cout << "Case #" << qq << ": ";
		testcase();
	}
	return 0;
}
/*
6 1597352862016328480
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3548kb

input:

1 1
X

output:

-1.0000000000
-1
(1, 1)


result:

wrong answer read -1.000000 but expected 0.000000, error = 1.000000