| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 758041 |
2023-06-14T05:33:34 Z |
Dexva |
Towers (NOI22_towers) |
C++14 |
|
2000 ms |
117168 KB |
#include <bits/stdc++.h>
using namespace std;
#define lln long long
void solve() {
lln n; cin >> n;
vector< pair<lln, lln> > points;
map<lln, vector<lln> > xs; //for each
map<lln, vector<lln> > ys;
map<lln, lln> xt;
map<lln, lln> yt;
for (lln i=0;i<n;i++) {
lln x, y; cin >> x >> y;
if (xs.find(x) != xs.end()) xs[x].push_back(i);
else {
vector<lln> nx; nx.push_back(i);
xs[x] = nx;
}
if (ys.find(y) != ys.end()) ys[y].push_back(i);
else {
vector<lln> ny; ny.push_back(i);
ys[y] = ny;
}
points.push_back(make_pair(x,y));
}
// for (const auto& x : xs) {
// vector<lln> xentry = x.second;
// cout << x.first << " | ";
// for (lln i=0;i<xentry.size();i++) cout << xentry[i] << " ";
// cout << '\n';
// }
// for (const auto& x : ys) {
// vector<lln> xentry = x.second;
// cout << x.first << " | ";
// for (lln i=0;i<xentry.size();i++) cout << xentry[i] << " ";
// cout << '\n';
// }
string ans = "";
for (lln i=0;i<n;i++) {
lln x = get<0>(points[i]), y = get<1>(points[i]);
//check the points on the same row (i.e., same y-value) as i, is i the one with least x or most x?
vector<lln> row = ys[y];
lln minx = i, maxx = i;
for (const auto& p : row) {
if (get<0>(points[p])<get<0>(points[minx])) minx = p;
if (get<0>(points[p])>get<0>(points[maxx])) maxx = p;
}
//check the points on the same column (i.e., same x-value) as i, is i the one with least y or most y?
vector<lln> col = xs[x];
lln miny = i, maxy = i;
for (const auto& p : col) {
if (get<1>(points[p])<get<1>(points[miny])) miny = p;
if (get<1>(points[p])>get<1>(points[maxy])) maxy = p;
}
// cout << "Point " << i << " " << minx << " " << maxx << " " << miny << " " << maxy << '\n';
if ((minx==i && miny==i) || (minx==i && maxy==i) || (maxx==i && miny==i) || (maxx==i && maxy==i)) {
ans += "1";
if (xt.find(x) != xt.end()) xt[x]++;
else xt[x] = 1;
if (yt.find(y) != yt.end()) yt[y]++;
else yt[y] = 1;
}
else if ((!(minx==i || maxx==i) && ys[y].size()==1 && xt[x]==1)) {
ans += "1";
}
else if ((!(miny==i || maxy==i) && xs[x].size()==1 && yt[y]==1)) {
ans += "1";
}
else ans += "0";
// (!(minx==i || maxx==i) && !(miny==i || maxy==i)) ans += "0";
// else ans += "1";
}
//2nd pass -- validating the 0s (no tower)
// for (lln i=0;i<n;i++) {
// lln x = get<0>(points[i]), y = get<1>(points[i]);
// if (ans[i]=='1') continue;
// bool surrounded = false;
// if (xt[x]==2 || yt[y]==2) surrounded = true;
// if (!surrounded) ans[i]='1';
// }
// for (const auto& k : ys) {
// lln yval = k.first;
// vector<lln> row = k.second;
// if (row.size()>1 && yt[yval]==1) {
// //smth is wrong
// }
// }
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while (t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
322 ms |
4560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2050 ms |
117168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
