oj.uz

답안 #378561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378561 2021-03-17T01:46:32 Z wiwiho Chessboard (IZhO18_chessboard) C++14
8 / 100
 39 ms 3180 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

ostream& operator<<(ostream& o, pll p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll iceil(ll a, ll b){
    return (a + b - 1) / b;
}

void checkcalc(ll l, ll r, ll t, pll c){
    ll even = 0, odd = 0;
    for(ll i = l; i <= r; i++){
        if(i / t % 2 == 0) even++;
        else odd++;
    }
    assert(mp(even, odd) == c);
}

pll calc(ll l, ll r, ll t){
    ll even = 0, odd = 0;

    if(l / t == r / t){
        if(l / t % 2 == 0) even = r - l + 1;
        else odd = r - l + 1;
        return mp(even, odd);
    }

    if(l / t % 2 == 0) even += iceil(l, t) * t - l;
    else odd += iceil(l, t) * t - l;
    l = iceil(l, t) * t;

    if(r / t % 2 == 0) even += r % t + 1;
    else odd += r % t + 1;
    r = r / t * t - 1;

    if(l > r) return mp(even, odd);

    int tmp = (r - l + 1) / t;
    if(l / t % 2 == 0) even += iceil(tmp, 2) * t, odd += tmp / 2 * t;
    else odd += iceil(tmp, 2) * t, even += tmp / 2 * t;

    return mp(even, odd);
}

vector<ll> xl, xr, yl, yr;
int n, k;
ll check(ll t){
    //cerr << "check " << t << "\n";
    ll b = 0, w = 0;
    for(int i = 0; i < k; i++){
        pll px = calc(xl[i], xr[i], t), py = calc(yl[i], yr[i], t);
        checkcalc(xl[i], xr[i], t, px);
        checkcalc(yl[i], yr[i], t, py);
        //cerr << i << " " << px << " " << py << " " << xl[i] << " " << xr[i] << " " << yl[i] << " " << yr[i] << "\n";
        b += px.F * py.F + px.S * py.S;
        w += px.S * py.F + px.F * py.S;
    }
    pll tp = calc(0, n - 1, t);
    ll tb = tp.F * tp.F + tp.S * tp.S;
    ll tw = tp.S * tp.F + tp.F * tp.S;
    //cerr << "check " << t << " " << b << " " << w << " " << tp << " " << tb << " " << tw << "\n";
    return min(tb - b + w, tw - w + b);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;

    xl.resize(k);
    xr.resize(k);
    yl.resize(k);
    yr.resize(k);
    for(int i = 0; i < k; i++){
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
        xl[i]--;
        yl[i]--;
        xr[i]--;
        yr[i]--;
    }

    ll ans = (ll) n * n;
    for(int t = 1; t * t <= n; t++){
        if(n % t) continue;
        if(t < n) ans = min(ans, check(t));
        if(n / t < n) ans = min(ans, check(t));
    }
    cout << ans << "\n";


    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2284 KB Output is correct
2 Correct 7 ms 876 KB Output is correct
3 Correct 18 ms 1516 KB Output is correct
4 Correct 18 ms 1772 KB Output is correct
5 Correct 23 ms 2156 KB Output is correct
6 Correct 15 ms 1388 KB Output is correct
7 Correct 4 ms 620 KB Output is correct
8 Correct 15 ms 1388 KB Output is correct
9 Correct 39 ms 3180 KB Output is correct
10 Correct 22 ms 1900 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2284 KB Output is correct
2 Correct 7 ms 876 KB Output is correct
3 Correct 18 ms 1516 KB Output is correct
4 Correct 18 ms 1772 KB Output is correct
5 Correct 23 ms 2156 KB Output is correct
6 Correct 15 ms 1388 KB Output is correct
7 Correct 4 ms 620 KB Output is correct
8 Correct 15 ms 1388 KB Output is correct
9 Correct 39 ms 3180 KB Output is correct
10 Correct 22 ms 1900 KB Output is correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -