Submission #490449

#TimeUsernameProblemLanguageResultExecution timeMemory
490449MohamedAliSaidaneHandcrafted Gift (IOI20_gift)C++14
0 / 100
156 ms30592 KiB
#include <bits/stdc++.h> #include "gift.h" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpi; typedef vector<pll> vpl; typedef vector<pld> vpd; #define pb push_back #define popb pop_back #define all(v) (v).begin(),(v).end() #define ff first #define ss second const ll MOD = 1e9 + 7; const ll INF = 1e18; int nx[4] = {1,-1,0,0}, ny[4] = {0,0,1,-1}; /////// SOLUTION \\\\\\\ int n, r; vi a, b, x; vi p, rnk; int findset(int x){return p[x] == x? x: findset(p[x]);} void unite(int i, int j) { int x= findset(i); int y = findset(j); if(x == y) return ; if(rnk[x] > rnk[y]) swap(x,y); if(rnk[x] == rnk[y]) rnk[y]++; p[x]= y; return; } int construct(int N, int R, vi A, vi B, vi X) { n = N, r = R; a.resize(r), b.resize(r), x.resize(r); p.assign(n,0); rnk.assign(n,0); string res = ""; for(int i = 0; i <n; i ++) res += 'R'; int x1 = 0, x2 = 0; for(int i = 0; i< r; i ++) { if(X[i] == 1) x1 ++; else x2 ++; } if(x1 == r) { return 1; craft(res); } if(x2 == r) { for(int i= 1;i <n; i += 2) res[i] = 'B'; craft(res); return 1; } for(int i = 0; i <n; i ++) p[i] = i; for(int i= 0; i <r; i ++) { a[i] = A[i]; b[i] = B[i]; x[i] = X[i]; if(x[i] == 1) for(int u = a[i]+1; u <= b[i]; u ++) unite(a[i],u); } for(int i= 0;i <r; i ++) { if(x[i] == 2) { int motif = findset(a[i]); bool flag = false; for(int j = a[i]+1; j <= b[i]; j ++) if(findset(j) != motif) flag = true; if(flag) continue; else return 0; } } int motif = findset(0); char prev = 'R'; for(int j = 0; j <n; j ++) { if(findset(j) != motif) { motif = findset(j); prev = prev == 'R'? 'B': 'R'; } res[j] = prev; } craft(res); return 1; }

Compilation message (stderr)

gift.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | /////// SOLUTION \\\\\\\
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...