| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1041633 | Requiem | Dominance (CEOI08_dominance) | C++17 | 7 ms | 756 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "antA"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 6e3 + 9;
const int MAXD = 1e9 + 1;
struct Ant{
char type;
int x, y, r;
} Ant[MAXN];
int ansBlack = 0, ansWhite = 0;
int width, height, n;
int mahattan(int x1, int y1, int x2, int y2){
return abs(x1 - x2) + abs(y1 - y2);
}
void rot(int &x1, int &y1){
int x2 = x1 + y1;
int y2 = y1 - x1;
x1 = x2, y1 = y2;
}
vector<ii> listVal;
/**
(x, y) --> (x + y, y - x)
Ve ban chat thi viec ta xoay toa do nhu vay no se tao
thanh 2 loai hinh vuong la hinh vuong le va chan.
Ta se giai cho tung hinh vuong chan va le.
Ta co the dua hinh vuong chan va le kich thuoc 2 thanh hinh vuong doi dai canh
kich thuoc 1 bang cach dich 0/1 xong chia 2.
Voi 1 hinh vuong, ta dem kieu gi,
Dau tien ta tach no thanh cac truc toa do.
Tiep theo ta duyet cac cai event
Neu no la black thi cho no -1
Neu no la white thi cho no +1
Co toi da 6000 event theo chieu ngang
Co toi da 6000 vi tri dang luu y theo chieu doc.
Voi 1 cai thang thi ta se biet hinh chu nhat ma no chiem.
**/
namespace subtask1{
bool check(){
return width <= 100 and height <= 100 and n <= 100;
}
void solve(){
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
// listVal.pb({i, j});
int numBlack = 0, numWhite = 0;
for(int k = 1; k <= n; k++){
if (mahattan(Ant[k].x, Ant[k].y, i, j) <= Ant[k].r){
listVal.pb({i, j});
if (Ant[k].type == 'W') numWhite++;
if (Ant[k].type == 'B') numBlack++;
}
}
cout << numBlack << ' ' << numWhite << endl;
if (numBlack > numWhite) ansBlack++;
if (numWhite > numBlack) ansWhite++;
}
}
cout << ansWhite << ' ' << ansBlack <<endl;
}
}
struct Event{
int x; //hoang do duong thang
int y1, y2, val; //khoang tung do
bool operator < (const Event &other) const{
return x < other.x;
}
};
namespace subtask2{
bool check(){
return true;
}
vector<Event> odd, even;
void findSquare(int x, int y, int r, int val){
ii TraiTren = ii(x - r, y + r);
ii TraiDuoi = ii(x - r, y - r);
ii PhaiTren = ii(x + r, y + r);
ii PhaiDuoi = ii(x + r, y - r);
if (TraiTren.fi&1) {
// cout << "ODD: " << endl;
// cout << x << ' ' << y << ' ' << r << endl;
// cout << "TRAI TREN: " << TraiTren.fi << ' ' << TraiTren.se << endl;
// cout << "TRAI DUOI: " << TraiDuoi.fi << ' ' << TraiDuoi.se << endl;
// cout << "PHAI TREN: " << PhaiTren.fi << ' ' << PhaiTren.se << endl;
// cout << "PHAI DUOI: " << PhaiDuoi.fi << ' ' << PhaiDuoi.se << endl;
odd.pb({x - r, y - r, y + r + 2, val});
odd.pb({x + r + 2, y - r, y + r + 2, -val});
}
else{
// cout << "EVEN: " << endl;
// cout << x << ' ' << y << ' ' << r << endl;
// cout << "TRAI TREN: " << TraiTren.fi << ' ' << TraiTren.se << endl;
// cout << "TRAI DUOI: " << TraiDuoi.fi << ' ' << TraiDuoi.se << endl;
// cout << "PHAI TREN: " << PhaiTren.fi << ' ' << PhaiTren.se << endl;
// cout << "PHAI DUOI: " << PhaiDuoi.fi << ' ' << PhaiDuoi.se << endl;
even.pb({x - r, y - r, y + r + 2, val});
even.pb({x + r + 2, y - r, y + r + 2, -val});
}
}
int getVal(int y, vector<int> &listY){
return lower_bound(listY.begin(), listY.end(), y) - listY.begin();
}
int valueAtPosition[MAXN];
void sweep(int Lx, int Rx, vector<int> &listVal){
int ans = 0, curValue = 0;
// cout << "SWEEPDATA" << endl;
// for(int i = 0; i < listVal.size(); i++){
// cout << listVal[i] << ' ';
// }
// cout << endl << endl;
for(int i = 0; i < listVal.size() - 1; i++){
int curY = listVal[i];
int nxtY = listVal[i + 1];
curValue += valueAtPosition[i];
// cout << "SWEEP " << valueAtPosition[i] << " " << i << ' ' << curY << ' ' << nxtY << endl;
// if (curValue != 0) cout << "DELTA: " << curValue <<' ' << (nxtY - curY) / 2 * (Rx - Lx) / 2 << endl;
if (curValue > 0) ansWhite += (nxtY - curY) / 2 * (Rx - Lx) / 2;
else if (curValue < 0) ansBlack += (nxtY - curY) / 2 * (Rx - Lx) / 2;
}
// cout << ansWhite << ' ' << ansBlack << endl;
// cout << endl;
}
void solveOne(vector<Event> event){
vector<int> listY;
for(int i = 0; i < event.size(); i++){
listY.pb(event[i].y1);
listY.pb(event[i].y2);
}
sort(listY.begin(), listY.end());
listY.erase(unique(listY.begin(), listY.end()), listY.end());
// cout << "VALUE: " << endl;
// for(int i = 0; i < listY.size(); i++){
// cout << listY[i] << ' ';
// }
// cout << endl;
sort(event.begin(), event.end());
for(int i = 0, j = 0; i < event.size(); i = j){
j = i;
while(j < event.size() and event[j].x == event[i].x) {
int yLeft = getVal(event[j].y1, listY);
int yRight = getVal(event[j].y2, listY);
// cout << "UPD: " << yLeft << ' ' << yRight << ' ' << event[j].val << endl;
valueAtPosition[yLeft] += event[j].val;
valueAtPosition[yRight] -= event[j].val;
j++;
}
int nxtX = ((j < (int) event.size()) ? event[j].x : event[i].x);
// cout << "RANGE: " << event[i].x << ' ' << nxtX << endl;
sweep(event[i].x, nxtX, listY);
// cout << endl;
}
}
void solve(){
//Voi 1 moi thang, ta tim 4 goc cua no.
// cout << n << endl;
for(int i = 1; i <= n; i++){
rot(Ant[i].x, Ant[i].y);
findSquare(Ant[i].x, Ant[i].y, Ant[i].r, ((Ant[i].type == 'W') ? 1 : -1));
findSquare(Ant[i].x, Ant[i].y, Ant[i].r - 1, ((Ant[i].type == 'W') ? 1 : -1));
}
solveOne(odd);
memset(valueAtPosition, 0, sizeof(valueAtPosition));
// cout << "ANS: " << ansWhite << ' ' << ansBlack << endl;
solveOne(even);
// cout << "ANS: " << ansWhite << ' ' << ansBlack << endl;
cout << ansWhite << ' ' << ansBlack << endl;
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> width >> height >> n;
for(int i = 1; i <= n; i++){
cin >> Ant[i].type >> Ant[i].x >> Ant[i].y >> Ant[i].r;
}
// if (subtask1::check()) return subtask1::solve(), 0;
// subtask1::solve();
// for(int i = 0; i < listVal.size(); i++){
// rot(listVal[i].fi, listVal[i].se);
// cout << '(' << listVal[i].fi << ',' << listVal[i].se << ')' << endl;
// }
if (subtask2::check()) return subtask2::solve(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||