답안 #72193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72193	2018-08-26T05:53:21 Z	내일_개학이다_ㅠㅠ(#2230, mAng0)	흔한 자료구조 문제 (FXCUP3_easy)	C++17	0 / 100	4 ms	2004 KB

easy

#include<bits/stdc++.h>
using namespace std;

#define pp 131072

int tree[pp+pp];
int hi[100005];
int val[100005];
vector<int> v;
int dp[2][20];
int jr[131072];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<pp+pp;i++){
        tree[i] = -1;
    }
    jr[0] = 0;
    for(int i=1;i<pp;i++){
        jr[i] = jr[i/2] + 1;
    }
    for(int i=pp;i<pp+n;i++){
        scanf("%d", &tree[i]);
        hi[tree[i]] = i-pp;
    }
    for(int i=0;i<n;i++) val[i] = 0;
    for(int i=pp-1;i>=1;i--){
        tree[i] = min(tree[i*2], tree[i*2+1]);
        if(tree[i] > 0) val[hi[tree[i]]]++;
    }
    for(int i=0;i<m;i++){
        int l;
        scanf("%d", &l);
        v.clear();
        for(int j=0;j<l;j++){
            int su;
            scanf("%d", &su);
            v.push_back(hi[su]);
        }
        if(l == 1){
            printf("%d %d\n", v[0] + 1, v[0] + 1);
        }else{
            sort(v.begin(), v.end());
            bool found = false;
            for(int j=0;j<=val[v[0]];j++){
                int pl = v[0];
                if(j) pl = pl & (~(1 << (j-1)));
                if(v[0] & (1 << j)){
                    int now = (v[0] | ((1 << j) - 1)) + 1;
                    int lim = j;
                    int dd = 0;
                    bool valid = false;
                    for(int ii=1;ii<l;ii++){
                        if(ii == l-1){
                            int nxt = jr[v[ii]-now];
                            if(lim == nxt) break;
                            if(val[v[ii]] >= nxt && dd == 0 || (dd == 1 && lim > nxt)){
                                now += (1 << nxt);
                                printf("%d %d\n", pl+1, now);
                                valid = true;
                                break;
                            }
                        }else{
                            int nxt0 = jr[v[ii]-now];
                            int nxt = jr[v[ii+1]-now]-1;
                            int nxt2 = jr[(now & (-now))] - 1;
                            nxt = min(nxt, nxt2);
                            if(val[v[ii]] >= nxt && nxt0 <= nxt){
                                if(lim == nxt) break;
                                if(dd == 0){
                                    if(lim < nxt){
                                        lim = nxt;
                                        now += (1 << lim);
                                    }else{
                                        dd = 1;
                                        lim = nxt;
                                        now += (1 << lim);
                                    }
                                }else{
                                    if(lim > nxt){
                                        lim = nxt;
                                        now += (1 << lim);
                                    }else break;
                                }
                            }else break;
                        }
                    }
                    if(valid){
                        found = true;
                        break;
                    }
                }else{
                    int now = (v[0] | ((1 << j) - 1)) + 1;
                    if(now > v[1]) continue;
                    int lim = j;
                    bool valid = false;
                    for(int ii=1;ii<l;ii++){
                        if(ii == l-1){
                            int nxt = jr[v[ii] - now];
                            if(val[v[ii]] >= nxt && lim > nxt){
                                now += (1 << nxt);
                                valid = true;
                                printf("%d %d\n", pl+1, now);
                                break;
                            }else{
                                break;
                            }
                        }else{
                            int nxt0 = jr[v[ii] - now];
                            int nxt = jr[v[ii+1]-now]-1;
                            if(nxt0 <= nxt && lim > nxt && val[v[ii]] >= nxt){
                                lim = nxt;
                                now += (1 << lim);
                            }else{
                                break;
                            }
                        }
                    }
                    if(valid){
                        found = true;
                        break;
                    }
                }
            }
            if(!found){
                printf("-1\n");
            }
        }
    }
}

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:58:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                             if(val[v[ii]] >= nxt && dd == 0 || (dd == 1 && lim > nxt)){
                                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~
easy.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &tree[i]);
         ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &l);
         ~~~~~^~~~~~~~~~
easy.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &su);
             ~~~~~^~~~~~~~~~~

Subtask #1

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1912 KB	Correct
2	Incorrect	4 ms	2004 KB	Wrong
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1912 KB	Correct
2	Incorrect	4 ms	2004 KB	Wrong
3	Halted	0 ms	0 KB	-