Submission #530782

#TimeUsernameProblemLanguageResultExecution timeMemory
530782Leo121Archery (IOI09_archery)C++14
80 / 100
82 ms2144 KiB
#include <bits/stdc++.h> #include <iostream> #include <limits.h> #include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> #include <string> #include <utility> #include <vector> #include <queue> #include <set> #include <unordered_set> #include <map> #define pb push_back #define bg(v) v.begin() #define all(v) bg(v), v.end() #define mp make_pair #define fi first #define se second #define forn(i, a, b) for(int i=int(a);i<=int(b);++i) #define fora(i, a, b) for(int i=int(a);i>=int(b);--i) #define lb lower_bound #define ub upper_bound using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpii; const int mod = 1e9 + 7; const int movi[4] = {1, -1, 0, 0}; const int movj[4] = {0, 0, -1, 1}; const int lim = 1e5; struct ura{ bool primero, segundo, actual; }; int n, r, res, minimo; int posiciones[2 * lim + 2]; bool ocupados[lim + 2]; vector<ura> casillas; int menor(int pos){ forn(i, 1, n){ ocupados[i] = 0; } int llevados = 0; fora(i, n, 2){ if(!casillas[i - 1].actual && !casillas[i - 1].primero){ llevados ++; } if(!casillas[i - 1].segundo){ llevados ++; } if(llevados){ ocupados[i] = 1; llevados --; } } if(!casillas[0].actual && !casillas[0].primero){ llevados ++; } if(!casillas[0].segundo){ llevados ++; } fora(i, n, 2){ if(!llevados){ break; } if(!ocupados[i]){ ocupados[i] = 1; llevados --; } } fora(i, pos, 2){ if(!ocupados[i]){ return i; } } fora(i, n, pos){ if(!ocupados[i]){ return i; } } } int mayor(int pos){ bool actual = 0; bool primero, segundo, agarrarinteresado = 0; int unos = 0; forn(i, 1, 2 * n){ if(casillas[i - 1].primero){ unos ++; primero = 1; } if(casillas[i - 1].segundo){ unos ++; } if(casillas[i - 1].actual){ actual = 1; if(i == 1){ agarrarinteresado = 1; } } if(i == 1){ if(unos == 2){ primero = segundo = 1; } else if(unos == 1){ primero = 1; } else{ segundo = 0; } } else{ if(unos > 1){ segundo = 1; } else if(unos == 1){ if(!primero){ segundo = 1; swap(segundo, primero); } else{ if(actual){ agarrarinteresado = 1; } segundo = 0; } } else{ if(actual){ agarrarinteresado = 1; } segundo = 0; } } if(primero && segundo){ unos --; casillas.pb({(bool) 1, (bool) 0, (bool) 0}); } else if(primero){ if(agarrarinteresado){ if(i >= n){ return (n - ((r - i) % n)); } casillas.pb({(bool) 0, (bool) 0, 1}); actual = agarrarinteresado = 0; } else{ casillas.pb({(bool) 0, (bool) 0, 0}); } } else{ casillas.pb({(bool) 0, (bool) 0, 1}); } } return 1; } int ronda(int pos){ casillas.clear(); forn(i, 1, pos - 1){ casillas.pb({(posiciones[i * 2] < posiciones[1]) ? (bool) 1 : (bool) 0, (posiciones[i * 2 + 1] < posiciones[1]) ? (bool) 1 : (bool) 0, (bool) 0}); } casillas.pb({(bool) 0, (posiciones[pos * 2] < posiciones[1]) ? (bool) 1 : (bool) 0, (bool) 1}); forn(i, pos + 1, n){ casillas.pb({(posiciones[i * 2 - 1] < posiciones[1]) ? (bool) 1 : (bool) 0, (posiciones[i * 2] < posiciones[1]) ? (bool) 1 : (bool) 0, (bool) 0}); } ///forn(i, 1, n){ /// cout << casillas[i - 1].primero << " " << casillas[i - 1].segundo << " " << casillas[i - 1].actual << "\n"; ///} return (posiciones[1] < n + 2) ? mayor(pos) : menor(pos); } int bs(){ int li = 1, ls = n, mitad, auxiliar, res, posres; if(posiciones[1] < n + 2){ posres = n; res = ronda(n); while(li <= ls){ mitad = (li + ls) / 2; auxiliar = ronda(mitad); if(auxiliar > res){ li = mitad + 1; } else{ ls = mitad - 1; res = auxiliar; posres = mitad; } } res = ronda(posres); li = posres + 1; ls = n; while(li <= ls){ mitad = (li + ls) / 2; auxiliar = ronda(mitad); if(auxiliar == res){ posres = mitad; li = mitad + 1; } else{ ls = mitad - 1; } } } else{ posres = 1; while(li <= ls){ mitad = (li + ls) / 2; auxiliar = ronda(mitad); if(auxiliar > mitad){ li = mitad + 1; } else{ posres = mitad; ls = mitad - 1; } } res = ronda(posres); li = posres + 1; ls = n; while(li <= ls){ mitad = (li + ls) / 2; auxiliar = ronda(mitad); if(auxiliar == res){ posres = mitad; li = mitad + 1; } else{ ls = mitad - 1; } } } return posres; } /**int actuales[4002]; pii objetivos[2002]; void procesar(){ if(objetivos[1].se < objetivos[1].fi){ swap(objetivos[1].fi, objetivos[1].se); } int ultimo = objetivos[1].se; actuales[objetivos[1].se] = n; forn(i, 2, n){ if(objetivos[i].se > objetivos[i].fi){ swap(objetivos[i].fi, objetivos[i].se); } objetivos[i - 1].se = objetivos[i].se; actuales[objetivos[i].se] --; } objetivos[n].se = ultimo; } void armar(int primero){ int actual = 1, posicion; objetivos[primero].se = posiciones[1]; actuales[posiciones[1]] = primero; forn(i, 2, 2 * n){ if(actual == primero * 2){ actual ++; } posicion = actual / 2; if(actual % 2){ posicion ++; } if(actual % 2){ objetivos[posicion].fi = posiciones[i]; } else{ objetivos[posicion].se = posiciones[i]; } actuales[posiciones[i]] = posicion; actual ++; } } int arre[5]; int arre2[5]; void bruta(){ int auxiliar, res; forn(i, 1, n){ armar(i); forn(j, 1, r){ procesar(); } forn(j, 1, n){ if(objetivos[j].fi == posiciones[1] || objetivos[j].se == posiciones[1]){ auxiliar = j; } } arre2[i] = auxiliar; cout << auxiliar << " "; if(auxiliar < minimo){ minimo = auxiliar; } if(auxiliar == minimo){ res = i; } } cout << res << "\n"; }*/ int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ///cin >> n >> r; ///minimo = n; /**set<int> dif; n = 4; r = 11; forn(i, 1, 2 * n){ cin >> posiciones[i]; } forn(i, 1, 2 * n){ cout << posiciones[i] << " "; } cout << "\n"; cout << ronda(2); cout << "\n"; bruta();*/ cin >> n >> r; minimo = n; forn(i, 1, 2 * n){ cin >> posiciones[i]; } if(posiciones[1] == 1){ cout << n; return 0; } if(n == 1){ cout << 1; return 0; } cout << bs(); return 0; }

Compilation message (stderr)

archery.cpp: In function 'int menor(int)':
archery.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^
archery.cpp: In function 'int mayor(int)':
archery.cpp:140:20: warning: 'segundo' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |         if(primero && segundo){
      |            ~~~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...