oj.uz

Submission #840284

# Submission time Handle Problem Language Result Execution time Memory
840284 2023-08-31T09:25:42 Z Fysty Longest Trip (IOI23_longesttrip) C++17
15 / 100
 10 ms 308 KB 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

#include "longesttrip.h"

int n;


vector<int> longest_trip(int N,int D)
{
    n=N;
    vector<int> ret;
    if(D==3)
    {
        rep(i,n) ret.pb(i);
        return ret;
    }
    vector<int> v1={0},v2;
    bool has=1;
    rep1(i,n-1)
    {
        if(are_connected({v1.back()},{i}))
        {
            v1.pb(i);
            has=1;
        }
        else if(has==0)
        {
            v2.pb(i);
        }
        else
        {
            if(v2.empty()||are_connected({v2.back()},{i}))
            {
                v2.pb(i);
                has=0;
            }
            else
            {
                reverse(v2.begin(),v2.end());
                for(int x:v2) v1.pb(x);
                v2={i};
                has=1;
            }
        }
    }
    if(v1.size()<v2.size()) swap(v1,v2);
    if(v2.empty()) return v1;
    if(!are_connected(v1,v2)) return v1;
    if(are_connected({v1[0]},{v2[0]}))
    {
        reverse(v2.begin(),v2.end());
        for(int x:v1) v2.pb(x);
        return v2;
    }
    if(are_connected({v1.back()},{v2[0]}))
    {
        for(int x:v2) v1.pb(x);
        return v1;
    }
    if(are_connected({v1[0]},{v2.back()}))
    {
        for(int x:v1) v2.pb(x);
        return v2;
    }

    int l=0,r=(int)v1.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        vector<int> tmp;
        rep(i,mid+1) tmp.pb(v1[i]);
        if(are_connected(tmp,v2)) r=mid;
        else l=mid+1;
    }
    int id=l;

    l=0,r=(int)v2.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        vector<int> tmp;
        rep(i,mid+1) tmp.pb(v2[i]);
        if(are_connected({v1[id]},tmp)) r=mid;
        else l=mid+1;
    }

    for(int i=l;i<v2.size();i++) ret.pb(v2[i]);
    rep(i,l) ret.pb(v2[i]);
    reverse(v2.begin(),v2.end());
    for(int i=id;i<v1.size();i++) ret.pb(v1[i]);
    rep(i,id) ret.pb(v1[i]);
    return ret;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:107:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |         int mid=l+r>>1;
      |                 ~^~
longesttrip.cpp:118:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         int mid=l+r>>1;
      |                 ~^~
longesttrip.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=l;i<v2.size();i++) ret.pb(v2[i]);
      |                 ~^~~~~~~~~~
longesttrip.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=id;i<v1.size();i++) ret.pb(v1[i]);
      |                  ~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 8 ms 208 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 10 ms 208 KB Output is correct
8 Correct 9 ms 208 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 7 ms 208 KB Output is correct
12 Correct 8 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 8 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 6 ms 300 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct
9 Correct 8 ms 300 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 7 ms 208 KB Output is correct
12 Correct 6 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 9 ms 208 KB Output is correct
15 Correct 8 ms 208 KB Output is correct
16 Incorrect 1 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct
3 Correct 7 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 5 ms 208 KB Output is correct
9 Correct 9 ms 304 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 6 ms 208 KB Output is correct
12 Correct 4 ms 308 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 9 ms 208 KB Output is correct
15 Correct 6 ms 208 KB Output is correct
16 Incorrect 1 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -