# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
942689 | 2024-03-11T02:55:34 Z | guagua0407 | 건물 4 (JOI20_building4) | C++17 | 273 ms | 91432 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } const int inf=1e9; int main() {_ int n; cin>>n; n*=2; vector<vector<int>> vec(n,vector<int>(2)); for(int i=0;i<n;i++){ cin>>vec[i][0]; } for(int i=0;i<n;i++){ cin>>vec[i][1]; } vector<int> dir(n); for(int i=0;i<n;i++){ if(vec[i][0]>vec[i][1]){ swap(vec[i][0],vec[i][1]); dir[i]=1; } } vector<int> ans(n); ans[0]=dir[0]; for(int i=1;i<n;i++){ int prv=vec[i-1][ans[i-1]^dir[i-1]]; if(prv<=vec[i][0]) ans[i]=dir[i]; else if(prv<=vec[i][1]) ans[i]=dir[i]^1; else{ cout<<-1<<'\n'; return 0; } } int cur=0; for(int i=0;i<n;i++){ if(ans[i]==0) cur++; } //cout<<cur<<'\n'; for(int r=n-1;cur!=n/2 and r>=0;r--){ int l=r-1; while(l>=0 and (vec[l][0]<=vec[l+1][0] and vec[l][1]<=vec[l+1][1] and vec[l][1]>vec[l+1][0])){ l--; } l++; //cout<<l<<' '<<r<<'\n'; bool ok1=(l==0 or vec[l-1][ans[l-1]^dir[l-1]]<=vec[l][0]); bool ok2=(r==n-1 or vec[r][1]<=vec[r+1][ans[r+1]^dir[r+1]]); if(!ok1 or !ok2){ r=l; continue; } for(int i=l;i<=r;i++){ assert(ans[i]==dir[i]); } vector<pair<int,int>> dif; dif.push_back({0,r+1}); for(int i=r;i>=l;i--){ dif.push_back({dif.back().f+(dir[i]==0?-1:1),i}); } /*reverse(all(dif)); for(auto v:dif){ cout<<v.f<<' '<<v.s<<'\n'; }*/ sort(all(dif)); int pos; if(cur<=n/2){ pos=upper_bound(all(dif),make_pair(n/2-cur,inf))-dif.begin()-1; } else{ pos=lower_bound(all(dif),make_pair(n/2-cur,-inf))-dif.begin(); } int b=dif[pos].s; cur+=dif[pos].f; for(int i=r;i>=b;i--){ ans[i]=dir[i]^1; } r=l; } if(cur!=n/2){ //assert(false); cout<<-1<<'\n'; return 0; } //return 0; int sum=(ans[0]==0); for(int i=1;i<n;i++){ assert(vec[i-1][ans[i-1]^dir[i-1]]<=vec[i][ans[i]^dir[i]]); sum+=(ans[i]==0); } assert(sum==n/2); for(int i=0;i<n;i++){ cout<<(ans[i]==0?'A':'B'); } cout<<'\n'; return 0; } //maybe its multiset not set //yeeorz //laborz
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 604 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 600 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Correct | 1 ms | 740 KB | Output is correct |
12 | Correct | 1 ms | 604 KB | Output is correct |
13 | Correct | 1 ms | 720 KB | Output is correct |
14 | Correct | 2 ms | 600 KB | Output is correct |
15 | Correct | 1 ms | 604 KB | Output is correct |
16 | Correct | 2 ms | 604 KB | Output is correct |
17 | Correct | 2 ms | 604 KB | Output is correct |
18 | Correct | 1 ms | 604 KB | Output is correct |
19 | Correct | 1 ms | 600 KB | Output is correct |
20 | Correct | 1 ms | 604 KB | Output is correct |
21 | Correct | 1 ms | 604 KB | Output is correct |
22 | Correct | 1 ms | 604 KB | Output is correct |
23 | Correct | 1 ms | 604 KB | Output is correct |
24 | Correct | 1 ms | 604 KB | Output is correct |
25 | Correct | 1 ms | 604 KB | Output is correct |
26 | Correct | 1 ms | 604 KB | Output is correct |
27 | Correct | 1 ms | 604 KB | Output is correct |
28 | Correct | 1 ms | 684 KB | Output is correct |
29 | Correct | 1 ms | 604 KB | Output is correct |
30 | Correct | 1 ms | 604 KB | Output is correct |
31 | Correct | 1 ms | 604 KB | Output is correct |
32 | Correct | 1 ms | 464 KB | Output is correct |
33 | Correct | 1 ms | 600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 604 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 600 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Correct | 1 ms | 740 KB | Output is correct |
12 | Correct | 1 ms | 604 KB | Output is correct |
13 | Correct | 1 ms | 720 KB | Output is correct |
14 | Correct | 2 ms | 600 KB | Output is correct |
15 | Correct | 1 ms | 604 KB | Output is correct |
16 | Correct | 2 ms | 604 KB | Output is correct |
17 | Correct | 2 ms | 604 KB | Output is correct |
18 | Correct | 1 ms | 604 KB | Output is correct |
19 | Correct | 1 ms | 600 KB | Output is correct |
20 | Correct | 1 ms | 604 KB | Output is correct |
21 | Correct | 1 ms | 604 KB | Output is correct |
22 | Correct | 1 ms | 604 KB | Output is correct |
23 | Correct | 1 ms | 604 KB | Output is correct |
24 | Correct | 1 ms | 604 KB | Output is correct |
25 | Correct | 1 ms | 604 KB | Output is correct |
26 | Correct | 1 ms | 604 KB | Output is correct |
27 | Correct | 1 ms | 604 KB | Output is correct |
28 | Correct | 1 ms | 684 KB | Output is correct |
29 | Correct | 1 ms | 604 KB | Output is correct |
30 | Correct | 1 ms | 604 KB | Output is correct |
31 | Correct | 1 ms | 604 KB | Output is correct |
32 | Correct | 1 ms | 464 KB | Output is correct |
33 | Correct | 1 ms | 600 KB | Output is correct |
34 | Correct | 212 ms | 80960 KB | Output is correct |
35 | Correct | 210 ms | 77308 KB | Output is correct |
36 | Correct | 252 ms | 75868 KB | Output is correct |
37 | Correct | 216 ms | 77564 KB | Output is correct |
38 | Correct | 216 ms | 77528 KB | Output is correct |
39 | Correct | 230 ms | 77044 KB | Output is correct |
40 | Correct | 219 ms | 82528 KB | Output is correct |
41 | Correct | 243 ms | 86376 KB | Output is correct |
42 | Correct | 226 ms | 80588 KB | Output is correct |
43 | Correct | 237 ms | 83192 KB | Output is correct |
44 | Correct | 237 ms | 83272 KB | Output is correct |
45 | Correct | 232 ms | 83516 KB | Output is correct |
46 | Correct | 244 ms | 83388 KB | Output is correct |
47 | Correct | 241 ms | 82448 KB | Output is correct |
48 | Correct | 241 ms | 82236 KB | Output is correct |
49 | Correct | 273 ms | 83024 KB | Output is correct |
50 | Correct | 225 ms | 82512 KB | Output is correct |
51 | Correct | 225 ms | 82512 KB | Output is correct |
52 | Correct | 173 ms | 71900 KB | Output is correct |
53 | Correct | 172 ms | 71508 KB | Output is correct |
54 | Correct | 188 ms | 71528 KB | Output is correct |
55 | Correct | 174 ms | 71348 KB | Output is correct |
56 | Correct | 252 ms | 91432 KB | Output is correct |
57 | Correct | 208 ms | 79256 KB | Output is correct |
58 | Correct | 225 ms | 79664 KB | Output is correct |
59 | Correct | 220 ms | 87872 KB | Output is correct |
60 | Correct | 223 ms | 74172 KB | Output is correct |
61 | Correct | 235 ms | 79256 KB | Output is correct |
62 | Correct | 238 ms | 77980 KB | Output is correct |
63 | Correct | 250 ms | 79152 KB | Output is correct |
64 | Correct | 219 ms | 76444 KB | Output is correct |
65 | Correct | 228 ms | 79280 KB | Output is correct |