| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 312538 | mohamedsobhi777 | Mouse (info1cup19_mouse) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "grader.h"
#include<bits/stdc++.h>
using namespace std ;
int n, num ;
vector<int> per, ans ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> indi, goods ;
void del(int x){
goods.push_back(x) ;
for(int i = 0 ;i < (int) indi.size() ; ++ i){
if(indi[i] == x){
indi.erase(indi.begin() + i , indi.begin() + i + 1) ;
return ;
}
}
}
void print(){
for(int i = 0 ;i < n; ++ i)
cout<< ans[i] <<" " ;
cout<<".\n" ;
}
vector<int> nott[300] ;
bool ngood[400][400] ;
void anot(int x , int y){
ngood[x][y] = 1;
nott[x].push_back(y) ;
}
int epoch(){
int ret = 0 ;
for(int i = 0 ;i < n; ++ i){
int k = ans[i] ;
for(auto u : nott[i]){
if(k == u){
++ ret ;
break ;
}
}
}
}
bool good(vector<int> &vec){
return epoch() > (int) indi.size() / 2 ;
}
bool bad(int x, int y){
return ngood[x][ans[y]] + ngood[y][ans[x]] ;
}
int ovall(int x, int y){
int ret = 0 ;
for(int i = 0 ;i < n; ++ i){
ret += ngood[i][ans[i]] ;
}
ret += ngood[x][ans[y]] + ngood[y][ans[x]] ;
return ret ;
}
void solve(int n){
for(int i = 1;i <= n ; ++ i){
ans.push_back(i) ;
}
for(int i = 0 ;i < n; ++ i){
indi.push_back(i) ;
}
for(int i = 0 ;i < n; ++ i){
// int x ; cin >> x ;
// per.push_back(x) ;
}
random_shuffle(ans.begin() , ans.end() ) ;
int tim = 0 ;
int las = 0 ;
las = query(ans) ;
int tmr = 0 ;
while(tim ++ < 1000000){
int sz = (int) indi.size() ;
vector<pair<int,pii> > simu ;
for(int j = 0 ;j < 8 || simu.empty() ; ++ j){
int x = rng() % sz ;
int y = rng() % sz ;
if(x == y)continue ;
x = indi[x] ;
y = indi[y] ;
int ov = ovall(x , y) ;
simu.push_back({ov ,{x , y}}) ;
}
sort(simu.begin() , simu.end()) ;
int x = simu[0].second.first ;
int y = simu[0].second.second ;
tmr = 0 ;
swap(ans[x],ans[y]) ;
int now = query(ans) ;
if( abs(now - las) == 2){
del(x) ; del(y) ;
}else if(now == las + 1){
if(goods.size()){
int gud = goods.back() ;
vector<int> qu = ans ;
swap(qu[gud],qu[x]) ;
if(query(qu) == now - 2){
del(x) ;
}else{
del(y) ;
}
}
}else if(now == las -1 ){
if(goods.size()){
int gud = goods.back() ;
vector<int> qu = ans ;
swap(qu[x],qu[y]);
swap(qu[gud],qu[x]) ;
if(query(qu) == las - 2){
del(x) ;
}else{
del(y) ;
}
}
}else{
anot(x , ans[x]) ;
anot(x , ans[y]) ;
anot(y , ans[x]) ;
anot(y , ans[y]) ;
}
if(now < las)swap(ans[x],ans[y]) ;
las = max(las , now) ;
if(now == n)
break ;
}
return ;
if(las == n)
cout<<"ok " ;
else {
for(auto u : ans)cout<< u <<" " ;
cout<<"incorrect " ;
}
return ;
}