| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1153645 | enzy | Jousting tournament (IOI12_tournament) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int sp[maxn], marc[maxn], qtd, at[maxn];
vector<int>comeco[maxn], final[maxn];
pair<int,int> GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
set<pair<int,int>>caras;
for(int i=0;i<n;i++){
caras.insert({i,i});
comeco[i].clear(); final[i].clear();
sp[i]=at[i]=marc[i]=0;
}
vector<pair<int,pair<int,int>>>process;
for(int i=0;i<c;i++){
int l=s[i], r=e[i];
int cnt=0;
vector<pair<int,int>>aux;
for(auto p : caras){
if(l<=cnt&&cnt<=r) aux.push_back(p);
cnt++;
}
int idl=aux[0].first, idr=aux.back().second;
for(auto p : aux) caras.erase(p);
caras.insert({idl,idr});
process.push_back({i,{idl,idr}});
comeco[idl].push_back(i); final[idr].push_back(i);
//cout << idl << " " << idr << endl;
}
// começo supondo q o meu cara começa na pos 0
for(int i=1;i<n;i++){
sp[i]=sp[i-1];
if(k[i-1]>r) sp[i]++;
}
//for(int i=0;i<n;i++) cout << sp[i] << " ";
//cout << endl;
for(auto p : process){
int l=p.second.first, r=p.second.second, id=p.first;
if(l==0) marc[id]=sp[r];
else marc[id]=sp[r]-sp[l-1];
//cout << id << " " << marc[id] << endl;
}
int resp=0, best=0; qtd=0;
for(int i=0;i<n-1;i++){ // vou andando na pos q eu to brutando o meu cara
for(int a : comeco[i]){
at[a]++;
if(!marc[a]) qtd++;
}
if(qtd>best){
best=qtd;
resp=i;
}
if(i==n-1) break;
if(k[i]>r){ // esse cara vai da pos i+1, para a i
for(int a : comeco[i+1]){
marc[a]--;
if(marc[a]==0&&at[a]) qtd++;
}
for(int a : final[i]){
if(!marc[a]) qtd--;
marc[a]++;
}
}
for(int a : final[i]){
at[a]--;
if(!marc[a]) qtd--;
}
}
return {resp,best};
}
int main(){
int aux[]={0,3,2,1}, s[]={0,0}, e[]={3,1};
auto p=GetBestPosition(5,2,4,aux,s,e);
cout << "resposta-> " << p.first << " " << p.second << endl;
}