Codeforces Round #501 (Div. 3) // Rated

### Codeforces Round #501 (Div. 3) ###

### Rated : 1275 >> 1380  ###

< Solved > : 4 out of 7 ( A, B, C, E1)

A. Points in Segments

#include <cstdio>
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    int seg[101]={0};
 
    while(n--) {
        int l, r;
        scanf("%d%d", &l, &r);
        
        for(int i=l; i<=r; i++)
            seg[i] = 1;
    }
 
    int ans=0;
    for(int i=1; i<=m; i++)
        if(!seg[i])
            ans++;
    printf("%d\n", ans);
 
    for(int i=1; i<=m; i++)
        if(!seg[i])
            printf("%d ", i);
    puts("");
    return 0;
}

B. Obtaining the String

#include <cstdio>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    char s[55];
    char t[55];
    scanf("%s%s", s, t);
 
    int check[30]={0};
    for(int i=0; s[i]; i++) {
        check[s[i]-'a']++;
        check[t[i]-'a']--;
    }
 
    for(int i=0; i<26; i++) {
        if(check[i]) {
            puts("-1");
            return 0;
        }
    }
 
    vector<int> ans; 
    
    for(int i=0; i<n; i++) {
        while(s[i] != t[i]) {
            for(int k=i; k<n; k++) {
                if(s[k] == t[i]) {
                    char tmp = s[k-1];
                    s[k-1] = s[k];
                    s[k] = tmp;
                    ans.push_back(k);
                    break;
                }
            }
        }
    }
 
    int size = ans.size();
    if(size > 10000) puts("-1");
    else {
        printf("%d\n", size);
        for(int i=0; i<size; i++)
            printf("%d ", ans[i]);
        puts("");
    }
        
    return 0;
}
 
 

C. Songs Compression

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int b, s; };
typedef long long int lli;
 
 
bool cmp(P a, P b)
{
    return (a.b-a.s) > (b.b-b.s);
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    vector<P> v;
    lli sum=0LL;
    for(int i=0; i<n; i++) {
        int b, s;
        scanf("%d%d", &b, &s);
        v.push_back((P){b, s});
        sum += b;
    }
 
    sort(v.begin(), v.end(), cmp); 
    
    int ans=0;
    for(int i=0; i<n; i++) {
        if(sum > m) {
            ans++;
            sum = sum - (v[i].b-v[i].s);
        }
        else
            break;
    }
    
    if(ans == n && sum > m) ans = -1;
    printf("%d\n", ans);
    return 0;
}
 
 

E!. Stars Drawing (Easy Edition)

#include <cstdio>
#include <vector>
using namespace std;
 
struct P { int r, c, n; };
 
int n, m;
char g[1005][1005];
bool check[1005][1005];
 
int di[]={1, 0, -1, 0};
int dj[]={0, 1, 0, -1};
 
bool safe(int r, int c)
{
    return (0 < r && r <= n) && (0 < c && c <= m);
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    for(int i=1; i<=n; i++)
        scanf("%s", g[i]+1);
 
    vector<P> ans;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(g[i][j] == '*') {
                int size = 1;
                while(1) {
                    bool ok = 1;
                    for(int k=0; k<4; k++) {
                        int ni = i+di[k]*size;
                        int nj = j+dj[k]*size;
                        if(!safe(ni, nj) || g[ni][nj] != '*') {
                            ok = 0;
                            break;
                        }
                    }
                    if(ok) {
                        for(int k=0; k<4; k++) {
                            int ni = i+di[k]*size;
                            int nj = j+dj[k]*size;
                            check[ni][nj] = 1;
                        }    
                        check[i][j] = 1;
                        size++;
                    }
                    else {
                        if(size > 1) {
                            ans.push_back((P){i, j, size-1});
                        }
                        break;
                    }
                }
            }
        }
    }
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if((check[i][j] == 1 && g[i][j] == '.') || (check[i][j] == 0 && g[i][j] == '*')) {
                puts("-1");
                return 0;
            }
        }
    }
 
    int sz = ans.size();
    printf("%d\n", sz);
    for(int i=0; i<sz; i++) 
        printf("%d %d %d\n", ans[i].r, ans[i].c, ans[i].n);
 
    return 0;
}
 

>> '*' 을 찾으면 이 좌표 기준 상하좌우에 '*' 가 몇바퀴 나오는지, 이런 방식으로 구현했다. 

>> 시간복잡도는 O(n^3) 정도 되는것 같다.

-------------

D 는 웬지 시간만 조금 더 있었으면 할 수 있었을 거 같았는데, 핵당한 유저들이 많았다. E1 먼저 풀길 잘한듯..

E2 에서는 E1 코드를 그대로 제출했더니, pretest 43 에서 TLE...

F 얼필 봤을때, 할만해 보였는데, 시간 없었다...ㅜㅜ

### Tutorial : http://codeforces.com/blog/entry/60949 ###

< Solution >

A.

vector<int> cnt(m + 2);
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        ++cnt[l];
        --cnt[r + 1];
    }
    for (int i = 1; i <= m; ++i)
        cnt[i] += cnt[i - 1];
    
    vector<int> ans;
    for (int i = 1; i <= m; ++i) {
        if (cnt[i] == 0)
            ans.push_back(i);
    }

>> O(n+m) 풀이.

>> 쉽게 생각하면, L 번째에 1을 증가시키고, R+1 번째에 -1을 한다. 

>> 그러고 난 다음 L 부터 R+1 까지의 pSum 을 구하면 [L, R] 까지는 1이되고, R+1 번째는 0이 되서 원하는 답을 구할 수 있게 된다.

B.

vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (s[i] == t[i]) continue;
        int pos = -1;
        for (int j = i + 1; j < n; ++j) {
            if (s[j] == t[i]) {
                    pos = j;
                    break;
            }
        }
        if (pos == -1) {
            cout << -1 << endl;
            return 0;
        }
        for (int j = pos - 1; j >= i; --j) {
            swap(s[j], s[j + 1]);
            ans.push_back(j);
        }
    }

>> O(n^2)

>> 솔루션은 그위치를 찾은다음 i번째까지 거꾸로 스왑해나가는 풀이.

>> 반면에, 내 풀이는 한번스왑하면 다시 그곳을 찾아서 반복하는 것으로 좀 비효율적인 풀이다. (구현이 어렵지 않고, 시간이 시간인지라 이런식으로 해버렸다....ㅜㅜ)

C. 

>> O(blogs) because of sort.

>> 솔루션과 풀이거 거의 비슷하다.

E1. 

>> Um...