QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408720#5103. Fair DivisionberarchegasTL 0ms0kbC++143.4kb2024-05-10 21:55:152024-05-10 21:55:15

Judging History

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

  • [2024-05-10 21:55:15]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

13 382475111752106101

output:


result: