Submission #72942179

---

Source Code Expand

#include <bits/stdc++.h>
#include <random>
#include <algorithm>
#include <atcoder/all>
//#pragma GCC optimize("O")
//#pragma GCC optimize("O0")
//#pragma GCC optimize("O1")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Os")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Og")
#define rep(i,n) for(ll i=0;i<(ll)(n);++i)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)
#define rep2(i,m,n) for(ll i=(ll)(m);i<(ll)(n);++i)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;--i)
#define rrep1(i,n) for(ll i=(ll)(n);i>0;--i)
#define rrep2(i,m,n) for(ll i=(ll)(m);i>n;--i)
#define _GLIBCXX_DEBUG
#define _CRT_SECURE_NO_WARNINGS
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a));
#define RSORT(a) sort(rall(a));
#define REV(a) reverse(all(a));
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a),0LL)
#define lb(a,x) static_cast<int>(lower_bound(all(a),x)-a.begin())
#define ub(a,x) static_cast<int>(upper_bound(all(a),x)-a.begin())
#define SZ(a) ll(a.size())
#define CEIL(x,y) (x+y-1)/y
#define smallexpect(a,b) (a%smallMOD)*pow_mod(b,smallMOD-2,smallMOD)%smallMOD
#define bigexpect(a,b) (a%bigMOD)*pow_mod(b,bigMOD-2,bigMOD)%bigMOD
#define pf push_front
#define pb push_back
#define eb emplace_back
#define ppf pop_front()
#define ppb pop_back()
#define fi first
#define se second
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STRING(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHAR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DOUBLE(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
#define YES print("YES")
#define Yes print("Yes")
#define yes print("yes")
#define NO print("NO")
#define No print("No")
#define no print("no")
#define YESNO {print("YES");}else{print("NO");}
#define YesNo {print("Yes");}else{print("No");}
#define yesno {print("yes");}else{print("no");}
#define TA {print("Takahashi");}else{print("Aoki");}
#define nl {cout << '\n';}
#define nle {cerr << '\n';}

using namespace std;using namespace atcoder;
using ull=unsigned long long;using ll=long long;using ld=long double;using i7=__int128_t;
using pii=pair<int,int>;using pid=pair<int,ld>;using pis=pair<int,string>;using pll=pair<ll,ll>;
using pld=pair<ll,ld>;using pls=pair<ll,string>;using pdi=pair<ld,int>;using pdl=pair<ld,ll>;
using pdd=pair<ld,ld>;using pds=pair<ld,string>;using psi=pair<string, int>;using psl=pair<string,ll>;
using psd=pair<string,ld>;using pss=pair<string, string>;using mii=map<int, int>;using mid=map<int,ld>;
using mis=map<int,string>;using mll=map<ll,ll>;using mld=map<ll,ld>;using mls=map<ll,string>;using mli=map<ll,int>;
using mdi=map<ld,int>;using mdl=map<ld,ll>;using mdd=map<ld,ld>;using mds=map<ld,string>;using mil=map<int,ll>;
using msi=map<string, int>;using msl=map<string, ll>;using msd=map<string,ld>;using mss=map<string,string>;
using vi=vector<int>;using vi7=vector<i7>;using vs=vector<string>;using vl=vector<ll>;using vc=vector<char>;
using vb=vector<bool>;using vd=vector<ld>;using vpii=vector<pii>;using vpll=vector<pll>;using vpsi=vector<psi>;
using vpis=vector<pis>;using si=set<int>;using sl=set<ll>;using sc=set<char>;using ss=set<string>;
using sd=set<ld>;using vvi=vector<vi>;using vvi7=vector<vi7>;using vvl=vector<vl>;using vvc=vector<vc>;
using vvs=vector<vs>;using vvb=vector<vb>;using vvd=vector<vd>;using vvpii=vector<vpii>;using vvpll=vector<vpll>;
using vsi=vector<si>;using vsl=vector<sl>;using vvvi=vector<vvi>;using vvvi7=vector<vvi7>;using vvvl=vector<vvl>;
using vvvc=vector<vvc>;using vvvb=vector<vvb>;using vvvd=vector<vvd>;using mint=modint998244353;
using vvvvi=vector<vvvi>;using vvvvl=vector<vvvl>;using vvvvi7=vector<vvvi7>;using vvvvc=vector<vvvc>;
using vvvvb=vector<vvvb>;using vvvvd=vector<vvvd>;using vmii=vector<mii>;using vmil=vector<mil>;using vmli=vector<mli>;
using vmll=vector<mll>;using vmsi=vector<msi>;using vmsl=vector<msl>;using vmis=vector<mis>;using vmls=vector<mls>;
using vmss=vector<mss>;using vmid=vector<mid>;using vmdi=vector<mdi>;using vmdd=vector<mdd>;using vmld=vector<mld>;
using vmdl=vector<mdl>;using vmds=vector<mds>;using vmsd=vector<msd>;
using P=pair<ll, ll>;

void scan(){}
template<class T>void scan(vector<T> &v){
    for(T &t:v)cin>>t;
}
template<class T>void scan(vector<vector<T>> &v){
    for(auto &row:v)for(T&element:row)cin>>element;
}
template<class Head, class... Tail>void scan(Head &head, Tail &...tail){
    cin>>head;scan(tail...);
}
template<class T>void print(const T &t){
    cout<<t<<endl;
}
template<class Head,class...Tail>void print(const Head &head, const Tail &...tail){
    cout<<head;print(tail...);
}
template<class T>void vecout1(const vector<T> &v,char div='\n'){
    rep(i,v.size())cout<<v[i]<<(i==ll(v.size()-1)?div:' ');
}
template<class T>void vecout2(const vector<T> &v,char div='\n'){
    rep(i,v.size())cout<<v[i]<<div;
}
template<class T>void operator++(vector<T> &v,int){for(T &t:v)t++;}
template<class T>void operator--(vector<T> &v,int){for(T &t:v)t--;}
template<class T>void operator+=(vector<T> &v,T x){for(T &t:v)t+=x;}
template<class T>void operator-=(vector<T> &v,T x){for (T &t:v)t-=x;}
template<class T>void operator*=(vector<T> &v,T x){for(T &t:v)t*=x;}
template<class T>void operator/=(vector<T> &v,T x){for(T &t:v)t/=x;}
template<typename T>bool chmax(T &a, T b){return((a<b)?(a=b,true):(false));}
template<typename T>bool chmin(T &a, T b){return((a>b)?(a=b,true):(false));}
template<class T>void uni(T &a){
    sort(all(a));
    a.erase(unique(all(a)),a.end());
}

const ld PI=3.1415926535897932;
const int INF=INT_MAX-314159;const ll LINF=LLONG_MAX-3141592653;
const int bigMOD=1000000007;int smallMOD=998244353;
const int dx[]={-1,0,1,0,-1,1,1,-1};const int dy[]={0,1,0,-1,1,1,-1,-1};
const string ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alpha="abcdefghijklmnopqrstuvwxyz";
/*--------------------------------------------------------------------------------------------------------------------------
・Tターンまで全ショップを適当に巡回し続ける
・１０回りくらいしたら、たまにRに変えていく
・すべての店で持っている文字列をsetに入れておいて、含まれていない文字列になった時点で、最寄りの店に直行する。ただし逆行はしないように。
--------------------------------------------------------------------------------------------------------------------------*/
void solve(){
  ll N,M,K,T; cin >> N >> M >> K >> T;
  vvl to(N);

  rep(i,M) {
    ll a,b; cin >> a >> b;
    to[a].eb(b);
    to[b].eb(a);
  }
  rep(i,N) {
    ll dammyx, dammyy;
    cin >> dammyx >> dammyy;
  }
  set<string> sts;

  random_device rd;
  mt19937 mt(rd());
  uniform_int_distribution<int> distN(0, N-1);

  auto bfs = [&](ll from) -> vl {
    vvl vis(N);
    queue<ll> q;
    q.push(from);
    //    vis[from] = true;

    while (!q.empty()) {
      ll pr = q.front(); q.pop();
      for (ll ne: to[pr]) {
	if (vis[ne].size()) continue;
	vis[ne]=vis[pr];
	vis[ne].eb(ne);
	if (ne>=K) {
	  q.push(ne);
	  //	  vis[ne] = true;
	}
	else {
	  return vis[ne];
	}
      }
    }
    vl ret;
    return ret;
  };
  
  auto fout = [&](ll rst, ld rate) -> vl {

    vl ret;
    ll now = 0;
    ll pre = 0;
    ll numred=0;
    vb isred(N, false);
    sts.insert("W");
    string ice="";

    while (ret.size() < T) {
      if (now>=K && !isred[now] && ret.size()>rst) {
	if (ret.size()<T-1 && ret.size()%max(1LL, N-ll(numred*rate)) == 0) {
	  ret.eb(-1);
	  isred[now] = true;
	  numred++;
	}
      }

      if (now<K) {
	sts.insert(ice);
	ice = "";
      }
      else {
	ice += isred[now] ? "R" : "W";
	if (!sts.contains(ice)) {
	  vl route = bfs(now);
	  if (ret.size()< T-route.size() && route[0] != pre) {
	    for (auto e: route) ret.eb(e);
	    pre = now;
	    if (route.size()>1) pre = route[route.size()-2];
	    now = route.back();
	    continue;
	  }
	}
      }

      ll nx = distN(mt)%to[now].size();
      if (ret.size()>0 && to[now][nx] == pre) nx = (nx+1)%to[now].size();
      ret.eb(to[now][nx]);

      pre = now;
      now = to[now][nx];
    }
    
    return ret;
  };

  auto score = [&](vl cmd) -> ll {
    vector<set<string>> st(K);
    vb isred(N, false);
    string ice="";
    ll pre=0;
    for (auto now: cmd) {
      if (now == -1) {
	isred[pre] = true;
	continue;
      }
      if (now<K) {
	st[now].insert(ice);
	ice = "";
      }
      else {
	ice += isred[now] ? "R" : "W";
      }
      pre = now;
	
    }
    ll ret=0;
    rep(i,K) ret+=st[i].size();
    return ret;
  };


  vl ans;
  ll maxscr=0;
  rep(i,700) {
    ll rst = 100;// + 3000*i/50;
    ld rate = 1.1;// + 0.3*(i%100)/100;
    vl cand = fout(rst, rate);
    ll scr = score(cand);
    if (maxscr < scr) {
      ans = cand;
      maxscr = scr;
    }
  }

  if (ans.size() != T) cerr << "Invalid lines!\n";
  for (auto e: ans) cout << e << '\n';
  cerr << maxscr << endl;


}
/*--------------------------------------------------------------------------------------------------------------------------*/
int main(){
    cin.tie(nullptr);cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);
    srand((unsigned)time(NULL));

    solve();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In lambda function:
./Main.cpp:184:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  184 |     while (ret.size() < T) {
      |            ~~~~~~~~~~~^~~
./Main.cpp:185:46: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  185 |       if (now>=K && !isred[now] && ret.size()>rst) {
      |                                    ~~~~~~~~~~^~~~
./Main.cpp:186:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  186 |         if (ret.size()<T-1 && ret.size()%max(1LL, N-ll(numred*rate)) == 0) {
      |             ~~~~~~~~~~^~~~
./Main.cpp: In function 'void solve()':
./Main.cpp:261:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  261 |   if (ans.size() != T) cerr << "Invalid lines!\n";
      |       ~~~~~~~~~~~^~~~

Judge Result