답안 #699491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699491	2023-02-17T05:53:24 Z	cig32	즐거운 행로 (APIO20_fun)	C++17	31 / 100	131 ms	17056 KB

#include "bits/stdc++.h"
#include "fun.h"
using namespace std;

#include <vector>

std::vector<int> createFunTour(int N, int Q) {
  if(N == 2) return {0, 1};
  int rt=-1;
  int ma=-1;
  for(int i=0; i<N; i++) {
    int ab = attractionsBehind(0, i);
    if(N - ab <= N/2) {
      if(N - ab > ma) {
        ma=N - ab, rt=i;
      }
    }
  }
  assert(rt>=0);
  int dist[N];
  for(int i=0; i<N; i++) dist[i] = hoursRequired(rt, i);
  vector<int> leader;
  int M = 0;
  for(int i=0; i<N; i++) {
    if(dist[i] == 1) {
      M++;
      leader.push_back(i);
    }
  }
  priority_queue<pair<int, int> > depths[M];
  //cout << rt << "\n";
  vector<int> list[M];
  for(int i=0; i<N; i++) {
    int grp = M-1;
    for(int j=0; j<M-1; j++) {
      int hr = hoursRequired(leader[j], i);
      if(hr + 1 == dist[i]) {
        grp = j; break;
      }
    }
    depths[grp].push({dist[i], i});
    list[grp].push_back(dist[i]);
    //cout << "node " << i <<": group "<<grp<<"\n";
  }
  for(int i=0; i<M; i++) sort(list[i].begin(), list[i].end());
  //for(int i=0; i<M; i++) {
  //  for(int x: list[i]) cout << x << " ";
  //  cout << "\n";
  //}
  vector<int> ans;
  ma = -1;
  int id;
  for(int i=0; i<M; i++) {
    if((int) (depths[i].size()) > ma) {
      ma = depths[i].size();
      id = i;
    }
  }
  if(depths[id].size() <= N/2) {
    ma = -1;
    for(int j=0; j<M; j++) {
      if(depths[j].empty()) continue;
      if(depths[j].top().first > ma) {
        ma = depths[j].top().first, id = j;
      }
    }
  }
  ans.push_back(depths[id].top().second);
  depths[id].pop();
  //cout << ans[0] << " ";
  for(int i=0; i<N-1; i++) {
    ma = -1;
    int id2;
    for(int j=0; j<M; j++) {
      if(j == id) continue;
      int sz = depths[j].size();
      if(sz > ma) {
        ma = sz, id2 = j;
      }
    }
    if(depths[id2].size() <= (N-i-1) / 2) {
      ma = -1;
      for(int j=0; j<M; j++) {
        if(j == id) continue;
        if(depths[j].empty()) continue;
        if(depths[j].top().first > ma) {
          ma = depths[j].top().first, id2 = j;
        }
      }
    }
    ans.push_back(depths[id2].top().second);
    depths[id2].pop();
    id = id2;
    //cout << ans[i+1] << " ";
  }
  //cout << "\n";
  return ans;
}

Compilation message

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:59:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   if(depths[id].size() <= N/2) {
      |      ~~~~~~~~~~~~~~~~~~^~~~~~
fun.cpp:81:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     if(depths[id2].size() <= (N-i-1) / 2) {
      |        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fun.cpp:52:7: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |   int id;
      |       ^~
fun.cpp:73:9: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     int id2;
      |         ^~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	0 ms	272 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	296 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct

Subtask #2
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	0 ms	272 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	296 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	216 KB	Output is correct
23	Correct	0 ms	216 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	0 ms	300 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	220 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Incorrect	1 ms	340 KB	Repeated index
35	Halted	0 ms	0 KB	-

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	216 KB	Output is correct
11	Correct	0 ms	216 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	300 KB	Output is correct
18	Correct	115 ms	17056 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	2 ms	468 KB	Output is correct
21	Correct	3 ms	724 KB	Output is correct
22	Correct	6 ms	1236 KB	Output is correct
23	Correct	12 ms	2380 KB	Output is correct
24	Correct	17 ms	3088 KB	Output is correct
25	Correct	69 ms	9900 KB	Output is correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	300 KB	Output is correct
7	Correct	0 ms	300 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	220 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	9 ms	1748 KB	Output is correct
15	Correct	124 ms	16964 KB	Output is correct
16	Correct	131 ms	16820 KB	Output is correct
17	Correct	24 ms	4156 KB	Output is correct
18	Correct	57 ms	7828 KB	Output is correct
19	Correct	104 ms	13372 KB	Output is correct
20	Incorrect	4 ms	852 KB	Tour is not fun
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	0 ms	272 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	296 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	216 KB	Output is correct
23	Correct	0 ms	216 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	0 ms	300 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	220 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Incorrect	1 ms	340 KB	Repeated index
35	Halted	0 ms	0 KB	-

답안 #699491

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 34.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 34.0