QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#408720 | #5103. Fair Division | berarchegas | TL | 0ms | 0kb | C++14 | 3.4kb | 2024-05-10 21:55:15 | 2024-05-10 21:55:15 |
answer
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const int MAXN = 5e6 + 5;
const int INF = 1e9;
template<typename T>
using matrix = vector<vector<T>>;
using point = complex<int>;
vector<int> lista [int(1e4+5)];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> m >> n;
vector<point> mark;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
char c;
cin >> c;
if(c == 'X')
mark.push_back(point(i,j));
}
}
auto get_val =[&](point p) -> int {
if(p.real() == 0 && p.imag() == 0)
return 0;
p = point(p.imag(), p.real());
int d = max(abs(p.real()), abs(p.imag()));
int sq = (d*2-1)*(d*2-1);
if(p.real() == -1*d){
return sq+6*d-p.imag()+d-1;
}
if(p.imag() == d){
return sq+4*d-p.real()+d-1;
}
if(p.real() == d){
return sq+2*d + p.imag()+d-1;
}
return sq + p.real() + d-1;
};
// for(int i = -3; i <= 3; i++){
// for(int j = -3; j <= 3; j++){
// cout << point(i,j) << ' ' << get_val(point(i,j)) << '\n';
// }
// }
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < mark.size(); k++){
point cur = mark[k] - point(i,j);
lista[i*m+j].push_back(get_val(cur));
}
lista[i*m+j].push_back(INF);
sort(all(lista[i*m+j]),greater<int>());
// cerr << point(i,j) << ": ";
// for(int k : lista[i*m+j])
// cerr << k << ' ';
// cerr << endl;
}
}
const int l = max(n,m);
const int lim = l*l*5+10;
vector<int> poss(n*m);
iota(all(poss),0);
double expected = 0;
int mx = 0;
vector<int> mxocur;
auto bt =[&](vector<int> v, int time, auto && bt) -> void {
if(v.size() == 1){
expected+=time;
if(mx < time){
mx = time;
mxocur.clear();
}
if(mx == time){
mxocur.push_back(v.back());
}
return;
}
if(v.size() == 0){
return;
}
int mn = INF;
for(int i : v){
mn = min(mn, lista[i].back());
}
vector<int> good, bad;
for(int i : v){
if(lista[i].back() == mn){
lista[i].pop_back();
good.push_back(i);
} else {
bad.push_back(i);
}
}
v.clear();
bt(good,mn,bt);
bt(bad,mn,bt);
};
bt(poss,0,bt);
expected/=n*m;
cout << fixed << setprecision(6) << expected << '\n' << mx << '\n';
vector<point> resp;
for(int k : mxocur)
resp.push_back(point(k%m+1, n-k/m));
sort(all(resp), [&](point a, point b){
if(a.imag() == b.imag())
return a.real() < b.real();
return a.imag() < b.imag();
});
for(auto p : resp)
cout << p << ' ';
cout << '\n';
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
13 382475111752106101