QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#238944 | #7680. Subway | ucup-team346# | WA | 2ms | 6104kb | C++14 | 2.6kb | 2023-11-04 17:57:22 | 2023-11-04 17:57:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
int n;
vector <pair <int,int> > G[2005];
vector <pair <int,int> > li[2005][55],ans[55];
int lisy[2005],lc = 0;
void solve(){
cin >> n;
int mx = 0;
for(int i = 1;i <= n;i ++){
int x,y,a; cin >> x >> y >> a;
G[y + 1000].push_back(make_pair(x,a));
lisy[++ lc] = y;
mx = max(mx,a);
}
sort(lisy + 1,lisy + 1 + lc);
lc = unique(lisy + 1,lisy + 1 + lc) - lisy - 1;
for(int y = -1000;y <= 1000;y ++){
if(G[y + 1000].size() == 0) continue;
G[y + 1000].push_back(make_pair(-1001,mx)); G[y + 1000].push_back(make_pair(1001,mx));
sort(G[y + 1000].begin(),G[y + 1000].end());
int base_y = y * 60,lx = -1000000000 + 2000 * (1000 + 100);
if(y <= 0) base_y -= 100;
else base_y += 100;
for(int a = 1;a <= mx;a ++){
li[y + 1000][a].push_back(make_pair(-1000 - a,y));
li[y + 1000][a].push_back(make_pair(lx - 2000 * (1000 + a) + 1,base_y + a));
G[y + 1000].back().first = 1000 + a;
for(int j = 1;j < G[y + 1000].size();j ++){
if(G[y + 1000][j].second >= a){
int curx = G[y + 1000][j].first;
if(li[y + 1000][a].back().first != lx + 2000 * curx - 1) li[y + 1000][a].push_back(make_pair(lx + 2000 * curx - 1,base_y + a));
li[y + 1000][a].push_back(make_pair(curx,y));
if(j + 1 != G[y + 1000].size()) li[y + 1000][a].push_back(make_pair(lx + 2000 * curx + 1,base_y + a));
}
}
}
}
for(int i = 1;i <= lc;i ++){
int y = lisy[i];
int base_y = y * 60,rx = 1000000000;
if(y <= 0) base_y -= 100;
else base_y += 100;
for(int a = 1;a <= mx;a ++){
for(auto pi : li[y + 1000][a]) ans[a].push_back(pi);
ans[a].push_back(make_pair(rx - a,base_y + a - 1));
ans[a].push_back(make_pair(rx - a,base_y + 50));
}
}
cout << mx << '\n';
int sumsiz = 0;
map <pair <int,int>,int> mp;
for(int i = 1;i <= mx;i ++){
cout << ans[i].size();
sumsiz += ans[i].size();
for(auto [x,y] : ans[i]){ cout << ' ' << x << ' ' << y; mp[make_pair(x,y)] ++; }
cout << '\n';
}
// for(auto it = mp.begin();it != mp.end();it ++){
// cout << (it->first).first << ' ' << (it->first).second << ' ' << it->second << endl;
// }
assert(sumsiz <= 10000);
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 6104kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 27 -1001 1 -999801999 161 -997796001 161 2 1 -997795999 161 -995798001 161 1001 1 999999999 160 999999999 210 -1001 2 -999801999 221 -997798001 221 1 2 -997797999 221 -995798001 221 1001 2 999999999 220 999999999 270 -1001 3 -999801999 281 -997794001 281 3 3 -997793999 281 -995798001 281 1001 3 99...
result:
wrong answer Self-intersecting polyline 1.