| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1054289 |
2024-08-12T08:26:29 Z |
김은성(#11056) |
무지개나라 (APIO17_rainbow) |
C++14 |
|
230 ms |
22876 KB |
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
char dir[4] = {'N', 'E', 'S', 'W'};
vector<int> board[200009];
vector<tuple<int, int, int> > ran[200009];
int mx[200009];
int unf[200009];
int Find(int v){
if(unf[v]==v)
return v;
return unf[v] = Find(unf[v]);
}
void Union(int u, int v){
u = Find(u);
v = Find(v);
unf[v] = u;
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
board[sr].push_back(sc);
for(int i=0; i<M; i++){
int k;
for(k=0; k<4; k++){
if(S[i] == dir[k])
break;
}
sr += dr[k];
sc += dc[k];
board[sr].push_back(sc);
}
for(int i=1; i<=n; i++){
board[i].push_back(0), board[i].push_back(m+1);
sort(board[i].begin(), board[i].end());
board[i].erase(unique(board[i].begin(), board[i].end()), board[i].end());
}
}
bool overlap(tuple<int, int, int> u, tuple<int, int, int> v){
auto [s0, s1, e1] = u;
auto [e0, s2, e2] = v;
return (s2 <= e1 && s1 <= e2);
}
int colour2(int ar, int ac, int br, int bc) {
if(ar>br)
return 0;
int i, j, k;
for(i=ar; i<=br; i++){
//printf("i=%d board.size=%d\n", i,board[i].size());
for(j=0; j+1<board[i].size(); j++){
//printf("i=%d j=%d\n", i, j);
if(board[i][j+1] - board[i][j] >= 2 && max(board[i][j]+1, ac) <= min(board[i][j+1]-1, bc))
ran[i].push_back(make_tuple(-1, max(board[i][j]+1, ac), min(board[i][j+1]-1, bc)));
}
}
int ans = 0;
for(j=0; j<ran[ar].size(); j++)
get<0>(ran[ar][j]) = j;
mx[ar] = (int)ran[ar].size() - 1;
for(j=ar+1; j<=br; j++){
//printf("j=%d\n", j);
//printf("ran[j-1]=%d j=%d\n", ran[j-1].size(), ran[j].size());
vector<bool> ch(mx[j-1] + 1);
vector<int> inv(mx[j-1] + 1);
for(int k=0; k<=mx[j-1] + ran[j].size(); k++)
unf[k] = k;
for(int k=0; k<inv.size(); k++)
inv[k ]= -1;
int cnt = 0, p1 = 0, p2 = 0, last = 0;
while(p1 < ran[j-1].size() && p2 < ran[j].size()){
//printf("p1=%d p2=%d get=%d\n", p1, p2, get<0>(ran[j][p2]));
if(overlap(ran[j-1][p1], ran[j][p2])){
ch[get<0>(ran[j-1][p1])] = 1;
Union(get<0>(ran[j-1][p1]), p2 + mx[j-1] + 1);
}
if(p1+1 == ran[j-1].size()){
/*
for(int p = last; p <= p1; p++){
if(overlap(ran[j-1][p], ran[j][p2])){
if(inv[get<0>(ran[j-1][p])] != -1)
assert(inv[get<0>(ran[j-1][p])] == get<0>(ran[j][p2]));
inv[get<0>(ran[j-1][p])] = get<0>(ran[j][p2]);
}
}
if(get<0>(ran[j][p2]) == cnt)
cnt++;
*/
p2++;
//last = p1 = 0;
}
else
p1++;
}
vector<int> vec;
for(int k=0; k<ran[j].size(); k++){
get<0>(ran[j][k]) = Find(mx[j-1] + 1 + k);
vec.push_back(get<0>(ran[j][k]));
assert(get<0>(ran[j][k]) <= mx[j-1] || get<0>(ran[j][k]) == mx[j-1] + 1 + k);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
cnt= vec.size();
for(int k=0; k<ran[j].size(); k++){
get<0>(ran[j][k]) = lower_bound(vec.begin(), vec.end(), get<0>(ran[j][k])) - vec.begin();
}
//printf("j=%d cnt=%d\n", j, cnt);
mx[j] = cnt-1;
for(i=0; i<ch.size(); i++){
if(!ch[i])
ans++;
}
}
ans += mx[br] + 1;
return ans;
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0, i, j;
int last = ar-1;
for(i=ar; i<=br; i++){
if(upper_bound(board[i].begin(), board[i].end(), bc) - lower_bound(board[i].begin(), board[i].end(), ac) == bc-ac+1){
//printf("i=%d\n", i);
ans += colour2(last+1, ac, i-1, bc);
last = i;
}
}
ans += colour2(last+1, ac, br, bc);
return ans;
}
Compilation message
rainbow.cpp: In function 'bool overlap(std::tuple<int, int, int>, std::tuple<int, int, int>)':
rainbow.cpp:41:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | auto [s0, s1, e1] = u;
| ^
rainbow.cpp:42:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | auto [e0, s2, e2] = v;
| ^
rainbow.cpp: In function 'int colour2(int, int, int, int)':
rainbow.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(j=0; j+1<board[i].size(); j++){
| ~~~^~~~~~~~~~~~~~~~
rainbow.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(j=0; j<ran[ar].size(); j++)
| ~^~~~~~~~~~~~~~~
rainbow.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int k=0; k<=mx[j-1] + ran[j].size(); k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int k=0; k<inv.size(); k++)
| ~^~~~~~~~~~~
rainbow.cpp:71:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while(p1 < ran[j-1].size() && p2 < ran[j].size()){
| ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:71:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while(p1 < ran[j-1].size() && p2 < ran[j].size()){
| ~~~^~~~~~~~~~~~~~~
rainbow.cpp:77:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if(p1+1 == ran[j-1].size()){
| ~~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int k=0; k<ran[j].size(); k++){
| ~^~~~~~~~~~~~~~
rainbow.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int k=0; k<ran[j].size(); k++){
| ~^~~~~~~~~~~~~~
rainbow.cpp:109:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(i=0; i<ch.size(); i++){
| ~^~~~~~~~~~
rainbow.cpp:70:32: warning: unused variable 'last' [-Wunused-variable]
70 | int cnt = 0, p1 = 0, p2 = 0, last = 0;
| ^~~~
rainbow.cpp:48:12: warning: unused variable 'k' [-Wunused-variable]
48 | int i, j, k;
| ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:118:18: warning: unused variable 'j' [-Wunused-variable]
118 | int ans = 0, i, j;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
230 ms |
11604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
11100 KB |
Output is correct |
| 2 |
Correct |
22 ms |
20948 KB |
Output is correct |
| 3 |
Correct |
20 ms |
18928 KB |
Output is correct |
| 4 |
Correct |
20 ms |
19036 KB |
Output is correct |
| 5 |
Correct |
19 ms |
19156 KB |
Output is correct |
| 6 |
Correct |
28 ms |
22464 KB |
Output is correct |
| 7 |
Incorrect |
29 ms |
22876 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
230 ms |
11604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
230 ms |
11604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
