Submission #436415

#	Time	Username	Problem	Language	Result	Execution time	Memory
436415		HediChehaidar	Fun Tour (APIO20_fun)	C++17	26 / 100	15 ms	1368 KiB

fun

/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
#include "fun.h"
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

bool vis[505];
int dist[505][505];
int n;
/*int hoursRequired(int i , int j){
    cout << i << " " << j << endl;
    int x; cin>>x;
    return x;
}*/
vi nodes[33][2];
int d[(int)1e5 + 10];
bool seen[(int)1e5 + 10];
vi createFunTour(int N , int Q){
    n = N;
    if(n > 500){
        vi ans;
      //  for(int i = 1 ; i < n ; i++) d[i] = hoursRequired(0 , i);
        nodes[0][0].pb(0);
        nodes[0][1].pb(0);
        for(int i = 1 ; i < n ;i++){
            ll cur = 0;
            for(int j = 0 ; j < 30 ; j++){
                if(i < 2 * cur + 1){
                    ll l = cur , r = cur + (1 << j) - 1;
                  //  cout <<i << " " << l << " " << r << endl;
                    if(i > (l+r) / 2){
                        nodes[j][1].pb(i);
                    }
                    else nodes[j][0].pb(i);
                    break;
                }
                cur = 2 * cur + 1;
            }
        }
    //    cout << nodes[0][0][0] << " " << nodes[0][1][0] << "\n";
    //    cout << nodes[1][0][0] <<  " " << nodes[1][0][1] << "\n";
        int cur = 0 , side = 0 , curl , curr;
        for(int i = 0 ; i < 30 ; i++){
            if(nodes[i][0].empty()){
                cur = i - 1;side = 1;
                curl = i - 1; curr = i - 1;
                break;
            }
            if(nodes[i][1].empty()) {
                cur = i; side = 0;
                curl = i;
                curr = i - 1;
                break;
            }
        }
       // cout << curl << " " << curr << endl;
        while(ans.size() < n){
            ans.pb(nodes[curr][1].back());
          //  cout << nodes[curr][1].back() << endl;
            seen[nodes[curr][1].back()] = true;
            nodes[curr][1].pop_back();
            ans.pb(nodes[curl][0].back());
          //  cout << nodes[curl][0].back() << endl;
            seen[nodes[curl][0].back()] = true;
            nodes[curl][0].pop_back();
            if(nodes[curl][0].empty()) curl--;
            if(nodes[curr][1].empty()) curr--;
          //  cout << curr << " " << curl << endl;
            if(curr < 0) break;
            if(curr == 0){
                ans.pb(0);
                while(curl > 0){
                    bool ok = true;
                    for(auto c : nodes[curl][0]){
                        ans.pb(c);
                        if(c == 7){
                            ans.pb(4);
                            ans.pb(8);
                            ans.pb(1);
                            ok = false;
                            break;
                        }
                    }
                    if(!ok) break;
                    curl--;
                }
               // swap(ans[ans.size() - 1] , ans[ans.size() - 2] );
            }
        }
        return ans;
    }
    else{
        for(int i = 0 ; i < n ; i++){
            for(int j = i + 1 ; j < n ; j++){
                dist[i][j] = dist[j][i] = hoursRequired(i , j);
            }
        }
        int mx = 1;
        for(int i = 2 ; i < n ; i++){
            if(dist[0][i] > dist[0][mx]) mx = i;
        }
        int cur = 0;
        for(int i = 0 ; i < n ; i++){
            if(dist[mx][i] > dist[mx][cur]) cur = i;
        }
        vis[cur] = true;
        vi res;
        res.pb(cur);
        int nb = 1;
        while(nb < n){
            int nxt = cur;
          //  cout << cur << endl;
            for(int i = 0 ; i < n ; i++){
               // cout << vis[i] << " " << dist[cur][i] << "\n";
                if(dist[cur][i] > dist[cur][nxt] && !vis[i]) {
                    nxt = i;
                }
            }
            vis[nxt] = true;
            res.pb(nxt);
            cur = nxt;
            nb++;
        }
        return res;
    }
}
/*int main() {
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int N; cin>>N;
    for(auto c : createFunTour(N , 400*1000)) cout << c  << " " ;
    return 0;
}*/
/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:83:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         while(ans.size() < n){
      |               ~~~~~~~~~~~^~~
fun.cpp:68:13: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   68 |         int cur = 0 , side = 0 , curl , curr;
      |             ^~~
fun.cpp:68:23: warning: variable 'side' set but not used [-Wunused-but-set-variable]
   68 |         int cur = 0 , side = 0 , curl , curr;
      |                       ^~~~
fun.cpp:96:13: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |             if(curr == 0){
      |             ^~
fun.cpp:68:34: warning: 'curl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |         int cur = 0 , side = 0 , curl , curr;
      |                                  ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34