Submission #728582

#	Time	Username	Problem	Language	Result	Execution time	Memory
728582		grogu	Thousands Islands (IOI22_islands)	C++17	10 / 100	104 ms	12520 KiB

islands

#include "islands.h"
#include <iostream>
#include <vector>
#include <variant>
#include <set>
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define ll int
#define pll pair<ll,ll>
#define pb push_back
using namespace std;
#define maxn 405
ll n,m;
vector<ll> g[maxn];
ll id[maxn][maxn];
set<pll> sss;
vector<ll> gen(vector<ll> v){
    vector<ll> ans;
    for(ll i = 0;i<=v.size()/2-1;i++) ans.pb(v[i]);
    for(ll i = v.size()-1;i>=v.size()/2;i--) ans.pb(v[i]);
    for(ll i = v.size()/2 - 1;i>=0;i--) ans.pb(v[i]);
    for(ll i = v.size()/2;i<=v.size()-1;i++) ans.pb(v[i]);
    return ans;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N;
    m = M;
    for(ll &x : U) x++;
    for(ll &x : V) x++;
    if(n==2){
        vector<vector<ll> > cnt(3);
        for(ll i = 0;i<m;i++){
            ll x = U[i],y = V[i];
            cnt[x].pb(i);
        }
        bool ok = cnt[1].size()>=2&&cnt[2].size()>=1;
        if(!ok) return ok;
        ll x = cnt[1][0],y = cnt[1][1];
        ll z = cnt[2][0];
        vector<ll> ans;
        ans.pb(x);
        ans.pb(z);
        ans.pb(y);
        ans.pb(x);
        ans.pb(z);
        ans.pb(y);
        return ans;
    }
    for(ll i = 0;i<m;i++){
        ll x = U[i],y = V[i];
        g[x].pb(y);
        g[y].pb(x);
        id[x][y] = i;
        sss.insert({x,y});
    }
    if(n<=400&&sss.size()==n*(n-1)/2&&m==n*(n-1)/2){
        ll x = id[1][2];
        ll y = id[2][3];
        ll z = id[3][1];
        ll rx = id[2][1];
        ll ry = id[3][2];
        ll rz = id[1][3];
        vector<ll> ans = gen({x,y,z,rx,ry,rz});
        return ans;
    }

}

Compilation message (stderr)

islands.cpp: In function 'std::vector<int> gen(std::vector<int>)':
islands.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(ll i = 0;i<=v.size()/2-1;i++) ans.pb(v[i]);
      |                  ~^~~~~~~~~~~~~~
islands.cpp:19:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(ll i = v.size()-1;i>=v.size()/2;i--) ans.pb(v[i]);
      |                           ~^~~~~~~~~~~~
islands.cpp:21:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(ll i = v.size()/2;i<=v.size()-1;i++) ans.pb(v[i]);
      |                           ~^~~~~~~~~~~~
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:32:25: warning: unused variable 'y' [-Wunused-variable]
   32 |             ll x = U[i],y = V[i];
      |                         ^
islands.cpp:55:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if(n<=400&&sss.size()==n*(n-1)/2&&m==n*(n-1)/2){
      |                ~~~~~~~~~~^~~~~~~~~~~
islands.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45