제출 #295397

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
295397	2020-09-09 16:20:38	SeDunion	통행료 (IOI18_highway)	C++17	100 / 100	522 ms	13516 KiB

highway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int M;
const int MAXN = 2e5;
vector<pair<int,int>> g[MAXN];
vector<int> h[2],W;
ll dist;
// map<int,int> id[MAXN];
int find(vector<int>v) {
  int l = 0, r = v.size()-1;
  while (l <= r) {
    int m = (l + r) >> 1;
    for (int i = 0 ; i < M ; ++ i) {
      W[i] = 0;
    }
    for (int i = m ; i < v.size() ; ++ i) {
      for (auto [to,qaz] : g[v[i]]) {
        W[qaz] = 1;
        // W[id[V[i]][to]] = 1;
      }
    }
    if (ask(W)!=dist)l=m+1;
    else r=m-1;
  }
  return v[l-1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'int find(std::vector<int>)':
highway.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = m ; i < v.size() ; ++ i) {
      |                    ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31