oj.uz

Submission #85333

# Submission time Handle Problem Language Result Execution time Memory
85333 2018-11-19T10:58:10 Z mra2322001 Chessboard (IZhO18_chessboard) C++14
8 / 100
 69 ms 5456 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(ll i(0); i < (n); i++)
#define f1(i, n) for(ll i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const ll N = 100002;

ll n, k, f[N][2];
pair <ll, ll> a[N];
vector <vector <ll> > v;

ll mau(ll x, ll id){
    ll col = x%2;
    if(col==0 && id==0) col = 1;
    else if(col==1){
        col = id;
    }
    return col;
}

ll solve2(vector <pair <ll, ll> > cur, ll sz, ll id){
    ll Sz = cur.size();
    ll res = 0;
    for(ll i = 0; i < Sz - 1; i++){
        auto t = cur[i + 1];
        auto t2 = cur[i];
        ll x = cur[i + 1].first - cur[i].first;
        if(x==1){
            if(i==Sz - 2) break;
            if(cur[i + 1].first > (n/sz)) continue;
            ll col = mau(cur[i + 1].first, id);
            if(col==1) res = res + sz*sz - cur[i + 1].second;
            else res = res + cur[i + 1].second;
        }
        else{
            ll k1 = mau(cur[i].first + 1, id);
            ll k2 = mau(cur[i + 1].first - 1, id);
            ll y = cur[i + 1].first - cur[i].first - 1;
            if(k1 + k2 <= 1){
                y /= 2;
                res = res + (sz*sz)*y;
            }
            else{
                y = (y + 1)/2;
                res = res + (sz*sz)*y;
            }
            if(i + 1==ll(cur.size() - 1)) break;
            ll col = mau(cur[i + 1].first, id);
            if(col==1) res = res + sz*sz - cur[i + 1].second;
            else res = res + cur[i + 1].second;
        }
    }
    return res;
}

ll solve(ll s){
    f1(i, s) v[i].clear();
    f1(i, k){
        ll k1 = (a[i].first - 1)/s + 1;
        ll k2 = (a[i].second - 1)/s + 1;
        v[k1].emplace_back(k2);
    }
    vector <pair <ll, ll> > now;
    f1(i, (n/s)){
        now.clear();
        now.emplace_back(0, s*s);
        for(ll j = 0; j < v[i].size(); j++){
            ll cur = j;
            ll e = v[i][j];
            for(cur = j; cur < v[i].size(); cur++){
                if(v[i][cur] != v[i][j]) break;
            }
            now.emplace_back(v[i][j], cur - j);
            j = cur - 1;
            ll u = v[i][j];
            ll g = v[i][j];
        }
        now.emplace_back((n/s) + 1, s*s);
        f[i][0] = f[i][1] = 1e9;
        f[i][0] = solve2(now, s, 0);
        f[i][1] = solve2(now, s, 1);
    }
    ll x1 = 0, x2 = 0;
    f1(i, (n/s)){
        if(i%2) x1 = x1 + f[i][1], x2 = x2 + f[i][0];
        else x1 = x1 + f[i][0], x2 = x2 + f[i][1];
    }
    return min(x1, x2);
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    v.resize(n + 1);
    f1(i, k){
        ll x, y, u, v; cin >> x >> y >> u >> v;
        a[i] = {x, y};
    }
    sort(a + 1, a + k + 1);
    ll res = 21e8;
    f1(i, sqrt(n)){
        ll j = n/i;
        if(i*j==n){
            if(i != n)
            res = min(res, solve(i));
            if(j != n)
            res = min(res, solve(j));
        }
    }
    cout << res;
}

Compilation message

chessboard.cpp: In function 'll solve2(std::vector<std::pair<long long int, long long int> >, ll, ll)':
chessboard.cpp:26:14: warning: variable 't' set but not used [-Wunused-but-set-variable]
         auto t = cur[i + 1];
              ^
chessboard.cpp:27:14: warning: variable 't2' set but not used [-Wunused-but-set-variable]
         auto t2 = cur[i];
              ^~
chessboard.cpp: In function 'll solve(ll)':
chessboard.cpp:68:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll j = 0; j < v[i].size(); j++){
                       ~~^~~~~~~~~~~~~
chessboard.cpp:71:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(cur = j; cur < v[i].size(); cur++){
                          ~~~~^~~~~~~~~~~~~
chessboard.cpp:70:16: warning: unused variable 'e' [-Wunused-variable]
             ll e = v[i][j];
                ^
chessboard.cpp:76:16: warning: unused variable 'u' [-Wunused-variable]
             ll u = v[i][j];
                ^
chessboard.cpp:77:16: warning: unused variable 'g' [-Wunused-variable]
             ll g = v[i][j];
                ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 476 KB Output is correct
8 Correct 3 ms 524 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5320 KB Output is correct
2 Correct 14 ms 5320 KB Output is correct
3 Incorrect 41 ms 5456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5320 KB Output is correct
2 Correct 14 ms 5320 KB Output is correct
3 Incorrect 41 ms 5456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 476 KB Output is correct
8 Correct 3 ms 524 KB Output is correct
9 Correct 69 ms 5320 KB Output is correct
10 Correct 14 ms 5320 KB Output is correct
11 Incorrect 41 ms 5456 KB Output isn't correct
12 Halted 0 ms 0 KB -