이 문제를 처음 보았을때 인덱스를 통한 정렬을 생각을 하였는데 시간초를 계산해볼때 10만개의 배열에서
최악의 경우 계속 마지막 것만 물어보게 된다면 10만 *5000해서 5억정도의 시간이 걸릴 것 같아서 안되겠구나 하고
고민을 해보다 정 안되겠어서 다른 분들의 코드를 읽어보았는데 대부분 이 방식으로 푸신것 같습니다.
제 생각에서 어디가 잘못된 것이 있나요 ?... 아니면 테스트 케이스에서 마지막 것만 찾는 케이스가 없어서 그런건가요?.
#include <iostream>#include <algorithm>#include <vector>#include <string.h>#include <math.h>#include <queue>#include <set>#include <utility>#include <functional>#define MAX 4000005#define MOD 1000000007#pragma warning(disable:4996)using namespace std;
typedef struct st{ int num; int idx;}str1;
bool cmp(str1 a, str1 b) { return a.num < b.num;}
int n, k, i, j, cnt = 0, st, fi, target;str1 map[5000005];
int main(){ scanf("%d %d", &n, &k); for (i = 0; i < n; i++) { scanf("%d", &map[i].num); map[i].idx = i+1; } sort(map, map+n, cmp); for (i = 0; i < k; i++) { scanf("%d %d %d", &st, &fi, &target); for (j = 0; j < n; j++) { if (st <= map[j].idx && map[j].idx <= fi) cnt++; if(cnt == target) { printf("%d\n", map[j].num); break; } } cnt = 0; }}
https://www.acmicpc.net/board/...
카테고리를 질문으로 바꾸면 문제 번호와 소스코드를 넣는 칸이 있습니다.
죄송한데 그렇다면 5억의경우 코드를 간단하게 짜게된다면 1초안에 통과가 가능하다는 의미인가요?
초간단한 연산의 경우 10~20억 번도 가능합니다. https://www.acmicpc.net/proble... 이 문제의 경우 하나씩 연산하면 최대 10억 번 정도 반복문을 돌아야 하지만 약 600MS 정도에 통과되는 일이 있어 시간 제한이 1초에서 0.1초로 줄어들게 되었습니다.
댓글을 작성하려면 로그인해야 합니다.
s7d8f9 4년 전
이 문제를 처음 보았을때 인덱스를 통한 정렬을 생각을 하였는데 시간초를 계산해볼때 10만개의 배열에서
최악의 경우 계속 마지막 것만 물어보게 된다면 10만 *5000해서 5억정도의 시간이 걸릴 것 같아서 안되겠구나 하고
고민을 해보다 정 안되겠어서 다른 분들의 코드를 읽어보았는데 대부분 이 방식으로 푸신것 같습니다.
제 생각에서 어디가 잘못된 것이 있나요 ?... 아니면 테스트 케이스에서 마지막 것만 찾는 케이스가 없어서 그런건가요?.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <set>
#include <utility>
#include <functional>
#define MAX 4000005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;
typedef struct st
{
int num;
int idx;
}str1;
bool cmp(str1 a, str1 b) {
return a.num < b.num;
}
int n, k, i, j, cnt = 0, st, fi, target;
str1 map[5000005];
int main()
{
scanf("%d %d", &n, &k);
for (i = 0; i < n; i++)
{
scanf("%d", &map[i].num);
map[i].idx = i+1;
}
sort(map, map+n, cmp);
for (i = 0; i < k; i++)
{
scanf("%d %d %d", &st, &fi, &target);
for (j = 0; j < n; j++)
{
if (st <= map[j].idx && map[j].idx <= fi)
cnt++;
if(cnt == target)
{
printf("%d\n", map[j].num);
break;
}
}
cnt = 0;
}
}