oj.uz

Submission #312540

# Submission time Handle Problem Language Result Execution time Memory
312540 2020-10-13T16:48:40 Z mohamedsobhi777 Mouse (info1cup19_mouse) C++14
45 / 100
 3000 ms 8636 KB 
#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,pair<int,int> > > 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 ; 
}

Compilation message

mouse.cpp: In function 'int epoch()':
mouse.cpp:45:1: warning: no return statement in function returning non-void [-Wreturn-type]
   45 | }
      | ^
mouse.cpp: In function 'void solve(int)':
mouse.cpp:81:13: warning: variable 'tmr' set but not used [-Wunused-but-set-variable]
   81 |         int tmr = 0 ;
      |             ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Correct! Number of queries: 40
2 Correct 1 ms 384 KB Correct! Number of queries: 18
3 Correct 1 ms 384 KB Correct! Number of queries: 5
4 Correct 1 ms 384 KB Correct! Number of queries: 15
5 Correct 1 ms 384 KB Correct! Number of queries: 16
6 Correct 1 ms 384 KB Correct! Number of queries: 16

Subtask #2
31.99999 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Correct! Number of queries: 40
2 Correct 1 ms 384 KB Correct! Number of queries: 18
3 Correct 1 ms 384 KB Correct! Number of queries: 5
4 Correct 1 ms 384 KB Correct! Number of queries: 15
5 Correct 1 ms 384 KB Correct! Number of queries: 16
6 Correct 1 ms 384 KB Correct! Number of queries: 16
7 Correct 8 ms 384 KB Correct! Number of queries: 500
8 Correct 9 ms 540 KB Correct! Number of queries: 500
9 Correct 6 ms 384 KB Correct! Number of queries: 400
10 Correct 6 ms 384 KB Correct! Number of queries: 400
11 Correct 6 ms 384 KB Correct! Number of queries: 400
12 Correct 6 ms 392 KB Correct! Number of queries: 600
13 Correct 9 ms 384 KB Correct! Number of queries: 500
14 Correct 10 ms 384 KB Correct! Number of queries: 600
15 Correct 8 ms 384 KB Correct! Number of queries: 500
16 Correct 5 ms 396 KB Correct! Number of queries: 500

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Correct! Number of queries: 40
2 Correct 1 ms 384 KB Correct! Number of queries: 18
3 Correct 1 ms 384 KB Correct! Number of queries: 5
4 Correct 1 ms 384 KB Correct! Number of queries: 15
5 Correct 1 ms 384 KB Correct! Number of queries: 16
6 Correct 1 ms 384 KB Correct! Number of queries: 16
7 Correct 8 ms 384 KB Correct! Number of queries: 500
8 Correct 9 ms 540 KB Correct! Number of queries: 500
9 Correct 6 ms 384 KB Correct! Number of queries: 400
10 Correct 6 ms 384 KB Correct! Number of queries: 400
11 Correct 6 ms 384 KB Correct! Number of queries: 400
12 Correct 6 ms 392 KB Correct! Number of queries: 600
13 Correct 9 ms 384 KB Correct! Number of queries: 500
14 Correct 10 ms 384 KB Correct! Number of queries: 600
15 Correct 8 ms 384 KB Correct! Number of queries: 500
16 Correct 5 ms 396 KB Correct! Number of queries: 500
17 Execution timed out 3016 ms 8636 KB Time limit exceeded
18 Halted 0 ms 0 KB -