제출 #168591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168591		timothyhorsc	Chessboard (IZhO18_chessboard)	C++14	62 / 100	942 ms	8184 KiB

chessboard

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

#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define vi vector<int>
#define popcount __builtin_popcountll

const int INF = 1LL<<60;
const int MOD = 1000000007;

template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}

template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}

string bin_string(int x) {
    const int d = 64;
    string result(d, ' ');
    RREP(i, d-1, -1) result[d-1-i] = '0'+((x&1LL<<i)!=0);
    return result;
}

vector<int> getZ(string s) {
    int n = s.size();
    vector<int> z(n);
    int x = 0, y = 0;
    REP(i, 1, n) {
        z[i] = max(0LL, min(z[i-x], y-i+1));
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) {
            x = i;
            y = i+z[i];
            ++z[i];
        }
    }
    return z;
}

int powa(int base, int exp) {
    if (exp<=0) return 1;
    if (base<=0) return 0;
    int val = powa(base, exp>>1);
    val = val*val % MOD;
    if (exp&1) {
        val = val*base % MOD;
    }
    return val;
}

int n, k, res=INF;
vector<vi> blocks;

int bc(int d, int x1, int x2) {
    int firstb = x1/(2*d), lastb = x2/(2*d);
    int b = d*(lastb-firstb+1);
    firstb *= 2*d;
    lastb *= 2*d;
    b -= min(d, x1-firstb);
    b -= max(0LL, lastb+d-1-x2);
    return b;
}

bool getcost(int d) {
    int nd = n/d;
    int mincost = (nd*nd/2-k) * d*d;
    if (mincost >= res) return true;
    int cost = (nd*nd+1)/2 * d*d;
    for (vi block : blocks) {
        int x1=block[0],y1=block[1],x2=block[2],y2=block[3];
        --x1; --x2; --y1; --y2;
        int h = bc(d, x1, x2);
        int v = bc(d, y1, y2);
        int b = h*v + (x2-x1+1-h)*(y2-y1+1-v);
        int w = (x2-x1+1)*(y2-y1+1)-b;
        cost -= b;
        cost += w;
    }
    res = min(res, cost);
    res = min(res, n*n-cost);
    // cout << d << ": " << cost << ' ' << n*n-cost << '\n';
    return false;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> k;
    blocks.assign(k, vi(4));
    cin >> blocks;

    vi factors;
    for (int d=1; d*d<=n; ++d) {
        if (n%d==0) {
            factors.push_back(d);
            if (d*d!=n && d != 1) factors.push_back(n/d);
        }
    }
    sort(factors.rbegin(), factors.rend());
    for (int d : factors) {
        if (getcost(d)) break;
    }
    cout << res;
}

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp:109:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 0 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 0 / 30