Submission #1071800

#TimeUsernameProblemLanguageResultExecution timeMemory
1071800MihailoLongest Trip (IOI23_longesttrip)C++17
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define pll pair<long long, long long> #define MOD 1000000007ll #define xx first #define yy second using namespace std; typedef long long ll; mt19937 mt(169); bool are_connected(vector<int> A, vector<int> B); vector<int> sh; bool query(vector<int> a, vector<int> b) { vector<int> A, B; for(int i=0; i<a.size(); i++) A.pb(sh[a[i]]); for(int i=0; i<b.size(); i++) B.pb(sh[b[i]]); return are_connected(A, B); } int cur, zadnji, sled; bool nema; vector<int> put, klika; int ko(int jedan, vector<int> vise, int l, int r) { vector<int> a, b; a.pb(jedan); int m=(l+r)/2; for(int i=l; i<=m; i++) b.pb(vise[i]); if(query(a, b)) return ko(jedan, vise, l, m); else return ko(jedan, vise, m+1, r); } vector<int> longest_trip(int N, int D) { for(int i=0; i<N; i++) sh.pb(i); shuffle(sh.begin(), sh.end(), mt); cur=1; zadnji=1; put.pb(1); vector<int> a, b; while(zadnji<N-1) { a.clear(); b.clear(); if(klika.empty()) { a.pb(cur); b.pb(zadnji+1); if(query(a, b)) { cur++; put.pb(cur); zadnji=max(cur, zadnji); continue; } klika.pb(zadnji+1); nema=true; } else { sled=zadnji+1; if(nema) { a.pb(cur); b.pb(sled); if(query(a, b)) { cur=sled; put.pb(cur); zadnji=max(cur, zadnji); nema=false; } else { klika.pb(sled); zadnji=max(klika.back(), zadnji); } continue; } a.pb(cur); a.pb(sled); if(query(a, klika)) { a.pop_back(); if(!query(a, klika)) { cur=sled; put.pb(cur); zadnji=max(cur, zadnji); } sled=ko(cur, klika, 0, klika.size()-1); put.pb(sled); for(int i:klika) { if(i!=sled) { put.pb(i); cur=i; } } } } } return put; }

Compilation message (stderr)

longesttrip.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
longesttrip.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0; i<a.size(); i++) A.pb(sh[a[i]]);
      |                  ~^~~~~~~~~
longesttrip.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0; i<b.size(); i++) B.pb(sh[b[i]]);
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...