Thank you for participation and we hope you enjoy this round :)
D2A Submission is All You Need
Do you know the source of the title?
Assuming that choosing $$$\text{mex(S')}$$$ is optimal, what conditions does $$$S'$$$ need to satisfy?
Are there duplicate numbers in $$$S'$$$? Is there a number greater than $$$\text{mex(S')}$$$ in $$$S'$$$?
Assuming that choosing $$$\text{mex(S')}$$$ is optimal, there are no duplicate numbers in $$$S'$$$. And thers is not a number greater than $$$\text{mex(S')}$$$. Otherwise, we can easily construct a better answer.
Consider $$$\text{S={0,1,...,x}}$$$. We can see $$$\text{mex(S')} \gt \text{max(S')}$$$ when $$$x$$$ is $$$0$$$ or $$$1$$$. And $$$\text{mex({0,1})}=\text{mex({0})}+\text{sum({1})}$$$. Thus, we only use $$$\text{mex}$$$ operation for each single $$$0$$$.
The answer is $$$\text{sum(S)}$$$ add the number of $$$0$$$ in $$$S$$$.
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, tmp, ans = 0;
cin >> n;
for(int i=0; i<n; i++){cin >> tmp; ans += tmp + (tmp == 0);}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--) solve();
}
D2B Pathless
Casework. Consider two easy cases first: $$$\Sigma a \gt s$$$ and $$$\Sigma a=s$$$.
What if there is an index $$$i$$$ such that $$$a_i+a_{i+1}=1$$$?
To "block" $$$a_i+a_{i+1}=1$$$, what should Bob do?
Consider cases of $$$\Sigma a=s+1$$$ and $$$\Sigma a \gt s+1$$$.
The minimum path sum is the sum of the simple path from $$$1$$$ to $$$n$$$ (i.e., $$$1 \rightarrow 2 \rightarrow \dots \rightarrow n$$$), denoted as $$$\text{base_sum} = \sum_{i=1}^{n} a_i$$$.
The path can include back-and-forth movements (e.g., from $$$i$$$ to $$$i+1$$$ and back to $$$i$$$), which increases the path length and the path sum. Specifically, each back-and-forth movement between adjacent positions $$$(i, i+1)$$$ adds $$$a_i + a_{i+1}$$$ to the path sum.
Thus, the total path sum can be expressed as $$$\text{base_sum} + d$$$, where $$$d$$$ is the additional sum contributed by zero or more back-and-forth movements. Here, $$$d$$$ can be represented as a non-negative integer linear combination of the sums of adjacent pairs.
Casework:
If $$$s \lt \text{base_sum}$$$, no path sum can equal $$$s$$$ (since the base sum already exceeds $$$k$$$, and any additional movements will further increase the sum).
If $$$s = \text{base_sum}$$$, the simple path ($$$1 \rightarrow 2 \rightarrow \dots \rightarrow n$$$) already satisfies the condition, so Alice cannot be stopped.
If $$$s \gt \text{base_sum}$$$, let $$$d = s - \text{base_sum}$$$:
- If $$$d = 1$$$, we can rearrange the array to avoid adjacent pairs summing to $$$1$$$ (i.e., avoid $$$0$$$ and $$$1$$$ being adjacent). Specifically, place all $$$0$$$s first, followed by all $$$2$$$s, and then all $$$1$$$s (e.g., $$$[0, 0, \dots, 0, 2, 2, \dots, 2, 1, 1, \dots, 1]$$$). This ensures no adjacent pair sums to $$$1$$$, making $$$d = 1$$$ unachievable.
- If $$$d \neq 1$$$, no rearrangement can prevent Alice from achieving the path sum $$$s$$$ (since sums of adjacent pairs can cover all $$$T \geq 2$$$ through linear combinations).
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, k, tmp;
cin >> n >> k;
vector<int> a(3);
for(int i=0; i<n; i++){cin >> tmp; a[tmp]++;}
if(k == a[1] + 2*a[2] || k >= a[1] + 2*a[2] + 2){cout << -1 << '\n'; return;}
for(int i=0; i<a[0]; i++) cout << 0 << ' ';
for(int i=0; i<a[2]; i++) cout << 2 << ' ';
for(int i=0; i<a[1]; i++) cout << 1 << ' ';
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--) solve();
}
D1A Double Perspective
Assuming that choosing $$$S$$$ is optimal, what is the value of $$$g(S)$$$?
In the case of $$$g(S)=0$$$, make $$$f(S)$$$ the length of the union of the entire set.
Assuming that choosing $$$S$$$ is optimal, $$$g(S)$$$ must be $$$0$$$ because removing an edge on the cycle will not change $$$f(S)$$$.
In the case of $$$g(S)=0$$$, we need to make $$$f(S)$$$ the length of the union of the entire set. There are many approaches.
An easiest $$$O(n^2)$$$ approach is to remove all segments contained by other segments. Afterwards, it can be proven that there are no cycles with a length greater than or equal to $$$3$$$ in the graph. If there is a cycle, note it as $$$x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow ... \rightarrow x_1$$$, we can always find $$$x_{i-1} \lt x_i \gt x_{i+1}$$$, where either $$$[x_{i-1},x_i] \subseteq [x_i,x_{i+1}]$$$ or $$$[x_i,x_{i+1}] \subseteq [x_{i-1},x_i]$$$. At this point, we have deduced the contradiction, so there are no cycles with a length greater than or equal to $$$3$$$ in the graph.
Another approach is to use DSU to maintain the generate forest.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
int T,n;
int a[N],b[N];
void init()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
}
void solve()
{
vector<int> tag(n+4,1),ans;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(a[j]<=a[i]&&b[i]<=b[j]) tag[i]=0;
}
if(tag[i]) ans.push_back(i);
}
cout<<ans.size()<<"\n";
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
}
int main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
}
return 0;
}
D1B Stay or Mirror
Try to switch to the dark mode and read the statement.
Consider $$$p_i=1$$$. If $$$a_i=1$$$, what are inversions containing $$$i$$$? If $$$a_i=2n-1$$$, what are inversions containing $$$i$$$?
Attempt to generalize the conclusion to any pair $$$(i, j)$$$.
Consider $$$p_i=1$$$ and inversions containing $$$i$$$. If $$$a_i=1$$$, it is the minimum value, and the inversions containing $$$i$$$ are $$$(1, i), (2, i),... (i-1, i)$$$; If $$$a_i=2n-1$$$, it is the maximum value, and the inversions containing $$$i$$$ are $$$(i, i+1),... (i, n)$$$. The key observation is the number of inversions containing $$$i$$$ is only related to $$$a_i$$$, and completely unrelated to other elements.
At this point, the problem has actually been solved. We can greedily choose $$$\min(i-1,n-i)$$$ and remove $$$1$$$ from $$$p$$$, and the remaining part is a completely identical subproblem with a size of $$$n-1$$$.
It can be implemented as follows: for each index $$$i$$$, calculate the number of elements to the left that are bigger than $$$p_i$$$ (note it as $$$lbigger$$$), and the number of elements to the right that are bigger than $$$p_i$$$ (note it as $$$rbigger$$$). Then greedily add $$$\min(lbigger,rbigger)$$$ to the answer.
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, ans = 0;
cin >> n;
vector<int> p(n);
for(int i=0; i<n; i++) cin >> p[i];
for(int i=0; i<n; i++){
int left = 0, right = 0;
for(int j=0; j<i; j++) if(p[j] > p[i]) left++;
for(int j=i+1; j<n; j++) if(p[j] > p[i]) right++;
ans += min(left, right);
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--) solve();
}
D1C1 Interactive RBS (Easy Version), D1C2 Interactive RBS (Medium Version) and D1C3 Interactive RBS (Hard Version)
Try to Perform binary search to find a $$$\texttt{'('}$$$ and a $$$\texttt{')'}$$$ using $$$O(\log n)$$$ queries. It is best to complete it within $$$10$$$ operations (to pass the hard version).
Consider the easy version. Constraint implies that we use one query to determine $$$2$$$ characters.
Construct a string $$$x$$$, insert $$$s_i$$$ and $$$s_j$$$ into certain positions of $$$x$$$ to obtain string $$$y$$$, so that $$$f(y)$$$ can produce $$$4$$$ different values.
Consider the medium version. Effectively utilizing the conditions of $$$k \le 1000$$$.
Consider binary code.
Consider the hard version. The number of substrings in a string of length $$$l$$$ is $$$O(l ^ 2)$$$. How to utilize this?
At first, we need to find $$$s_x=\texttt{’(’}$$$ and $$$s_y=\texttt{’)’}$$$. Do binary search to find the smallest $$$i$$$ such that $$$f(s_1s_2...s_i) \gt 0$$$. Then we get $$$s_{i-1}=\texttt{’(’}$$$ and $$$s_i=\texttt{’)’}$$$. A corner case is $$$f(s)=0$$$. In this case, $$$s_n=\texttt{’(’}$$$ and $$$s_1=\texttt{’)’}$$$.
Ask $$$f(\texttt{"s1)s2)()"})$$$:
If $$$f(\texttt{"s1)s2)()"})=6$$$, $$$s_1=$$$ $$$\texttt{'('}$$$ and $$$s_2=$$$ $$$\texttt{'('}$$$.
If $$$f(\texttt{"s1)s2)()"})=2$$$, $$$s_1=$$$ $$$\texttt{'('}$$$ and $$$s_2=$$$ $$$\texttt{')'}$$$.
If $$$f(\texttt{"s1)s2)()"})=3$$$, $$$s_1=$$$ $$$\texttt{')'}$$$ and $$$s_2=$$$ $$$\texttt{'('}$$$.
If $$$f(\texttt{"s1)s2)()"})=1$$$, $$$s_1=$$$ $$$\texttt{')'}$$$ and $$$s_2=$$$ $$$\texttt{')'}$$$.
In this way, we can determine two characters with one query.
Read the tutorial in easy version first.
Note $$$f_0$$$ as the $$$f$$$ value of the following string:
$$$\underbrace{()()\ldots()}_{128 pairs}$$$ $$$)$$$ $$$\underbrace{()()\ldots()}_{64 pairs}$$$ $$$)$$$ $$$\dots$$$ $$$)()$$$
Then ask for the $$$f$$$ value of the following string (note it as $$$f_1$$$):
$$$\underbrace{s_8)()\ldots()}_{128 pairs}$$$ $$$)$$$ $$$\underbrace{s_7)()\ldots()}_{64 pairs}$$$ $$$)$$$ $$$\dots$$$ $$$)s_1)$$$
By checking the binary bits of $$$f_0-f_1$$$, we can determine $$$8$$$ positions with one query. For example, if $$$f_0-f_1=(10000101)_2$$$, we can get $$$s_1=s_3=s_8='('$$$.
Read the tutorial of the medium version first.
We can optimize
$$$\underbrace{s_i)()\ldots()}_{2^k pairs}$$$
to
$$$\underbrace{()()\ldots()}_{2^{\lfloor \frac{k}{2} \rfloor}-1\ pairs}$$$ $$$s_i)$$$ $$$\underbrace{()()\ldots()}_{2^{\lceil \frac{k}{2} \rceil}-1\ pairs}$$$
With this optimization, we can determine $$$12$$$ locations in one query.
Another construction also works:
$$$\underbrace{s_1)s_1)\ldots s_1)}_{g(1)\ pairs}$$$ $$$)$$$ $$$\underbrace{s_2)s_2)\ldots s_2)}_{g(2)\ pairs}$$$ $$$)$$$ $$$\underbrace{s_3)s_3)\ldots s_3)}_{g(3)\ pairs}$$$ $$$)$$$ $$$\ldots$$$ $$$\underbrace{s_{12})s_{12})\ldots s_{12})}_{g(12)\ pairs}$$$
where $$$g(i) \gt g(1)+g(2)+\ldots+g(i-1)$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const long long kk = 1000;
const long long ml = kk * kk;
const long long mod = ml * kk + 7;
const long long inf = ml * ml * ml + 7;
#define T(x, i) get<i>(x)
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define forn(i, n) for (int i = 0; i < n; i++)
template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.F >> p.S; }
template<class T, class U> inline ostream& operator<<(ostream& str, const pair<T, U> &p) { str << p.F << ' ' << p.S << ' '; return str; }
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
template<class T> inline ostream& operator<<(ostream& str, const vector<T> &a) { for (auto &i : a) str << i << ' '; return str; }
void flush() { cout << flush; }
void flushln() { cout << endl; }
template<class T> void read(T &x) { cin >> x; }
template<class T, class ...U> void read(T &x, U&... u) { read(x); read(u...); }
template<class T> void print(const T &x) { cout << x; }
template<class T, class ...U> void print(const T &x, const U&... u) { print(x); print(u...); }
template<class ...T> void println(const T&... u) { print(u..., '\n'); }
template<class T> void eprint(const T &x) { cerr << x; }
template<class T, class ...U> void eprint(const T &x, const U&... u) { eprint(x); eprint(u...); }
template<class ...T> void eprintln(const T&... u) { eprint(u..., '\n'); }
#ifdef DEBUG
mt19937 rng(1033);
#define var(x) cerr << #x << ": " << x << '\n';
#define range(a, b) cerr << #a << ", " << #b << ": "; for (auto _it = a; _it != b; ++_it) cerr << *_it << ' '; cerr << '\n';
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define cerr if (false) cerr
#define var(x)
#define range(a, b)
#define eprintln if(false)eprintln
#define eprint if(false)eprint
#endif
int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }
int n;
map<vector<int>, int> mem;
int ask(vector<int> ind) {
if (!mem.count(ind)) {
cout << "? ";
cout << ind.size() << ' ';
for (auto i : ind)
cout << i + 1 << ' ';
cout << endl;
int res;
cin >> res;
mem[ind] = res;
}
return mem[ind];
}
bool same(vector<int> ind) {
if (ask(ind))
return false;
ind.push_back(ind[0]);
ind.erase(ind.begin());
if (ask(ind))
return false;
return true;
}
pii search(vector<int> ind) {
if (ind.size() == 2) {
if (ask(ind))
return {ind[0], ind[1]};
return {ind[1], ind[0]};
}
vector<int> inda, indb;
int sz = (ind.size() + 1) / 2;
for (int i = 0; i < sz; i++) {
inda.push_back(ind[i]);
indb.push_back(ind[ind.size() - 1 - i]);
}
if (!same(inda))
return search(inda);
if (!same(indb))
return search(indb);
inda.push_back(indb[0]);
return search(inda);
}
pii find_reg2() {
vector<int> ind(n);
iota(all(ind), 0);
shuffle(all(ind), rng);
return search(ind);
}
void solve() {
mem.clear();
auto [po, pc] = find_reg2();
vector<int> to_ask(n);
iota(all(to_ask), 0);
if (to_ask.size() & 1)
to_ask.push_back(0);
string ans = string(n, '.');
ans[po] = '(';
ans[pc] = ')';
for (int i = 0; i < to_ask.size(); i += 2) {
int a = to_ask[i], b = to_ask[i + 1];
vector<int> q = {po, pc, po, a, b, pc};
int res = ask(q);
// ()(ab) - x ab
// ()(()) - 4 ()
// ()((() - 2 ((
// ()())) - 3 ))
// ()()() - 6 )(
map<int, pair<char, char>> results = {
{4, {'(', ')'}},
{2, {'(', '('}},
{3, {')', ')'}},
{6, {')', '('}},
};
assert(results.count(res));
auto [resa, resb] = results[res];
ans[a] = resa;
ans[b] = resb;
}
cout << "! " << ans << endl;
}
signed main() {
#ifdef DEBUG
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
solve();
}
#ifdef DEBUG
cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}
/*
()(ab)
()(()) - 4 ()
()((() - 2 ((
()())) - 3 ))
()()() - 6 )(
2
3
)((
2
()
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define _int64 long long
#define mo 998244353
char tar[110000];
int cnt;
int doask(vector<int>& a)
{
int i,ret;
/*
{
int v,tmp,j;
string ss;
cnt++;
ss="";
for (i=0;i<a.size();i++)
{
ss.push_back(tar[a[i]]);
}
tmp=0;
for (i=0;i<ss.length();i++)
{
v=0;
for (j=i;j<ss.length();j++)
{
if (ss[j]=='(') v++;
else v--;
if (v<0) break;
if (v==0) tmp++;
}
}
return tmp;
}
*/
printf("? %d",(int)a.size());
for (i=0;i<a.size();i++)
printf(" %d",a[i]+1);
printf("\n");
fflush(stdout);
scanf("%d",&ret);
return ret;
}
char ans[1100];
void doanswer()
{
printf("! %s\n",ans);
cerr<<"T "<<tar<<endl;
cerr<<"cnt:"<<cnt<<endl;
if (string(ans)==string(tar))
{
cerr<<"good"<<endl;
}
else cerr<<"bad"<<endl;
fflush(stdout);
}
int main()
{
int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st;
vector<int> a;
scanf("%d",&t);
for (l=0;l<t;l++)
{
scanf("%d",&n);
for (i=0;i<n;i++)
{
x=rand()%2;
if (x==0) tar[i]='(';
else tar[i]=')';
}
tar[n]='\0';
cnt=0;
st=0;ans[n]='\0';
indl=-1;
indr=-1;
// while (st<n)
// {
ll=st;rr=n;
while (rr-ll>1)
{
mid=(ll+rr)/2;
a.clear();
for (i=st;i<=mid;i++)
a.push_back(i);
tmp=doask(a);
if (tmp==0) ll=mid;
else rr=mid;
}
if (rr==n)
{
indr=st;
/*
if ((indl==-1)&&(indr==-1))
{
indr=st;
}
ll=st-1;rr=n;
while (rr-ll>1)
{
mid=(ll+rr)/2;
a.clear();
a.push_back(mid);
a.push_back(indr);
tmp=doask(a);
if (tmp==0) ll=mid;
else rr=mid;
}
for (i=st;i<=ll;i++)
ans[i]=')';
for (i=rr;i<n;i++)
ans[i]='(';
st=n;
break;
*/
}
else
{
indr=rr;
/*
v=rr;
ans[v]=')';
ll=st-1;rr=v-1;
while (rr-ll>1)
{
mid=(ll+rr)/2;
a.clear();
a.push_back(mid);
a.push_back(v);
tmp=doask(a);
if (tmp==0) ll=mid;
else rr=mid;
}
for (i=st;i<=ll;i++)
ans[i]=')';
for (i=rr;i<v;i++)
ans[i]='(';
st=v+1;
indl=v-1;
indr=v;
*/
}
// }
//cerr<<"indr:"<<indr<<endl;
for (i=0;i<n;i+=8)
{
a.clear();
for (j=0;j<8;j++)
{
if (i+j>=n) break;
for (k=0;k<(1<<j);k++)
{
a.push_back(i+j);
a.push_back(indr);
a.push_back(indr);
}
}
tmp=doask(a);
for (j=0;j<8;j++)
{
if (i+j>=n) break;
if (((1<<j)&tmp)!=0) ans[i+j]='(';
else ans[i+j]=')';
}
}
doanswer();
}
}
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define _int64 long long
#define mo 998244353
char tar[110000];
int cnt;
int doask(vector<int>& a)
{
int i,ret;
/*
{
int v,tmp,j;
string ss;
cnt++;
ss="";
for (i=0;i<a.size();i++)
{
ss.push_back(tar[a[i]]);
}
tmp=0;
for (i=0;i<ss.length();i++)
{
v=0;
for (j=i;j<ss.length();j++)
{
if (ss[j]=='(') v++;
else v--;
if (v<0) break;
if (v==0) tmp++;
}
}
return tmp;
}
*/
printf("? %d",(int)a.size());
for (i=0;i<a.size();i++)
printf(" %d",a[i]+1);
printf("\n");
fflush(stdout);
scanf("%d",&ret);
return ret;
}
char ans[1100];
void doanswer()
{
printf("! %s\n",ans);
cerr<<"T "<<tar<<endl;
cerr<<"cnt:"<<cnt<<endl;
if (string(ans)==string(tar))
{
cerr<<"good"<<endl;
}
else cerr<<"bad"<<endl;
fflush(stdout);
}
int main()
{
int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st,sum,len;
vector<int> a;
vector<int> p;
sum=0;len=0;
for (i=1;i<=130;i++)
{
tmp=i*(i+1)/2;
if (tmp>sum)
{
p.push_back(i);
//cerr<<"i:"<<i<<endl;
sum+=tmp;
len+=i+i;
}
}
//cerr<<"p.sz:"<<p.size()<<" "<<len<<endl;
scanf("%d",&t);
for (l=0;l<t;l++)
{
scanf("%d",&n);
for (i=0;i<n;i++)
{
x=rand()%2;
if (x==0) tar[i]='(';
else tar[i]=')';
}
tar[n]='\0';
cnt=0;
st=0;ans[n]='\0';
indl=-1;
indr=-1;
// while (st<n)
// {
ll=st;rr=n;
while (rr-ll>1)
{
mid=(ll+rr)/2;
a.clear();
for (i=st;i<=mid;i++)
a.push_back(i);
tmp=doask(a);
if (tmp==0) ll=mid;
else rr=mid;
}
if (rr==n)
{
indr=st;
/*
if ((indl==-1)&&(indr==-1))
{
indr=st;
}
ll=st-1;rr=n;
while (rr-ll>1)
{
mid=(ll+rr)/2;
a.clear();
a.push_back(mid);
a.push_back(indr);
tmp=doask(a);
if (tmp==0) ll=mid;
else rr=mid;
}
for (i=st;i<=ll;i++)
ans[i]=')';
for (i=rr;i<n;i++)
ans[i]='(';
st=n;
break;
*/
}
else
{
indr=rr;
/*
v=rr;
ans[v]=')';
ll=st-1;rr=v-1;
while (rr-ll>1)
{
mid=(ll+rr)/2;
a.clear();
a.push_back(mid);
a.push_back(v);
tmp=doask(a);
if (tmp==0) ll=mid;
else rr=mid;
}
for (i=st;i<=ll;i++)
ans[i]=')';
for (i=rr;i<v;i++)
ans[i]='(';
st=v+1;
indl=v-1;
indr=v;
*/
}
// }
//cerr<<"indr:"<<indr<<endl;
for (i=0;i<n;i+=p.size())
{
a.clear();
for (j=0;j<p.size();j++)
{
if (i+j>=n) break;
for (k=0;k<p[j];k++)
{
a.push_back(i+j);
a.push_back(indr);
}
a.push_back(indr);
}
tmp=doask(a);
for (j=p.size()-1;j>=0;j--)
{
if (i+j>=n) continue;
v=p[j]*(p[j]+1)/2;
if (tmp>=v)
{
tmp-=v;ans[i+j]='(';
}
else ans[i+j]=')';
}
}
doanswer();
}
}
D1D Permutation Blackhole
Consider enumerating $$$p_i = 1$$$. After that, will the cells to the left of $$$p_i$$$ affect the cells to the right of $$$p_i$$$?
Consider range DP.
Can you find the upper bound of $$$s_i$$$?
Consider range DP.
Note $$$dp[l][r][x][y]$$$ as the number of scheme ensureing $$$s[l-1]+=x$$$ and $$$s[r+1]+=y$$$.
Transform:
dp[l][r][x][y] = \left\{ \begin{array}{l} \Sigma_{\text{i is nearer to l}} \binom{r-l}{i-l} \cdot dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ + \Sigma_{\text{i is nearer to r}} \binom{r-l}{i-l} \cdot dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1]\ (s_i = -1) \\ \Sigma_{\text{i is nearer to l},\ j+k=s_i} \binom{r-l}{i-l}\cdot dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ + \Sigma_{ \text{i is nearer to r},\ j+k=s_i} \binom{r-l}{i-l}\cdot dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1]\ (s_i \neq -1) \end{array} \right.
$$$
For simplicity, this formula omits some edge cases. Readers are encouraged to fill in the details themselves.
The complexity seems high, but the problem can be solved with one key observation: the upper bound of $$$s_i$$$ is $$$O( \log n)$$$.
Proof: let's fix a position $$$i$$$ and only consider the cells $$$c_1, c_2, ..., c_k$$$ $$$(c_1 \lt c_2 \lt ... \lt c_k)$$$ to the left of $$$i$$$ that cause $$$s_i$$$ to increase. We can see that $$$i - c_j \gt 2(i - c_{j+1})$$$. Otherwise, $$$c_{j+1}$$$ would cause $$$s_{c_j}$$$ to increase by $$$1$$$ instead of $$$s_i$$$. Thus, We can get $$$k$$$ is $$$O( \log n)$$$.
Complexity: $$$O(n^3 \log^3n)$$$.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=110;
const int LOGN=10;
const ll TMD=998244353;
const ll INF=2147483647;
int T,n;
ll s[N],fac[N],inv[N];
ll dp[N][N][LOGN][LOGN];
void init_C()
{
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD;
inv[N-1]=pw(fac[N-1],TMD-2);
for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%TMD;
}
ll C(int n,int m)
{
if(n<m||n<0||m<0) return 0;
return fac[n]*inv[m]%TMD*inv[n-m]%TMD;
}
void init()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n+4;i++)
for(int j=1;j<=n+4;j++)
for(int ii=0;ii<LOGN;ii++)
for(int jj=0;jj<LOGN;jj++)
dp[i][j][ii][jj]=0;
dp[1][1][0][1]=(s[1]<1);
for(int i=2;i<=n;i++)
dp[i][i][1][0]=(s[i]<1);
for(int i=1;i<=n;i++) //auxiliary value
dp[i][i-1][0][0]=dp[i+1][i][0][0]=1;
}
int ABS(int x)
{
return x<0?-x:x;
}
void solve()
{
for(int i=2;i<=n;i++)
{
for(int j=1;j+i-1<=n;j++)
{
for(int ii=0;ii<LOGN;ii++)
{
for(int jj=0;jj<LOGN;jj++)
{
int l=j,r=j+i-1;
for(int k=l;k<=r;k++)
{
int tagl=0,tagr=0;
if(l==1&&r==n) tagl=tagr=0;
else if(l==1) tagr=1;
else if(r==n) tagl=1;
else
{
if(ABS(l-1-k)<=ABS(k-(r+1))) tagl=1;
else tagr=1;
}
if(ii-tagl<0||jj-tagr<0) continue;
if(s[k]==-1)
{
ll suml=0,sumr=0;
for(int kk=0;kk<LOGN;kk++) suml=(suml+dp[l][k-1][ii-tagl][kk])%TMD;
for(int kk=0;kk<LOGN;kk++) sumr=(sumr+dp[k+1][r][kk][jj-tagr])%TMD;
dp[l][r][ii][jj]=(dp[l][r][ii][jj]+suml*sumr%TMD*C(r-l,k-l))%TMD;
}
else
{
for(int kk=0;kk<LOGN;kk++)
{
if(s[k]-kk<0||s[k]-kk>=LOGN) continue;
dp[l][r][ii][jj]=(dp[l][r][ii][jj]+dp[l][k-1][ii-tagl][kk]*dp[k+1][r][s[k]-kk][jj-tagr]%TMD*C(r-l,k-l))%TMD;
}
}
}
}
}
}
}
cout<<dp[1][n][0][0]<<'\n';
}
int main()
{
fastio;
init_C();
cin>>T;
while(T--)
{
init();
solve();
}
return 0;
}
D1E Induced Graph Queries
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())
using ll=long long;
using u32=unsigned int;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f128=__float128;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vvc=vc<vc<T>>;
template<typename T> using vvvc=vc<vvc<T>>;
using vi=vc<int>;
using vll=vc<ll>;
using vvi=vc<vi>;
using vvll=vc<vll>;
#define vv(type,name,n,...) \
vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))
template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using max_heap=priority_queue<T>;
// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}
template<typename T>
void sort_unique(vector<T> &vec){
sort(vec.begin(),vec.end());
vec.resize(unique(vec.begin(),vec.end())-vec.begin());
}
template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}
template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif
template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}
template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}
vvi read_graph(int n, int m, int base=1){
vvi adj(n);
for(int i=0,u,v; i<m; ++i){
cin >> u >> v,u-=base,v-=base;
adj[u].pb(v),adj[v].pb(u);
}
return adj;
}
vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}
template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}
template<typename T> constexpr T inf=0;
template<> constexpr int inf<int> = 0x3f3f3f3f;
template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;
template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}
template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
//#include<atcoder/all>
//using namespace atcoder;
//using mint=modint998244353;
//using mint=modint1000000007;
const int N=1<<18,K=1<<10;
struct DS{
int big[N/K],small[N];
void ins(int x){
small[x]++;
big[x>>10]++;
}
void del(int x){
small[x]--;
big[x>>10]--;
}
int kth(int k){
k--;
int cur=0;
while(big[cur]<=k) k-=big[cur++];
cur<<=10;
while(small[cur]<=k) k-=small[cur++];
return cur;
}
}ds;
void ahcorz(){
int n,m; cin >> n >> m;
vvi adj=read_graph(n,m);
vi block(n);
int cur=0;
rep(n){
if(cur>=n) break;
int tot=0;
while(cur<n&&tot<K){
tot+=sz(adj[cur])+1;
block[cur++]=i;
}
}
int q; cin >> q;
vc<array<int,4>> qq(q);
vi res(q);
rep(q){
int l,r,k; cin >> l >> r >> k; l--,r--;
qq[i]={l,r,k,i};
}
sort(all(qq),[&](array<int,4> arr1, array<int,4> arr2){
if(block[arr1[0]]!=block[arr2[0]]) return block[arr1[0]]<block[arr2[0]];
if(block[arr1[0]]&1) return arr1[1]>arr2[1];
else return arr1[1]<arr2[1];
});
vi val(n);
int l=0,r=0;
ds.ins(0);
auto ins=[&](int i){
for(auto j: adj[i]){
if(j>=l&&j<=r){
ds.del(val[j]);
val[j]^=i+1,val[i]^=j+1;
ds.ins(val[j]);
}
}
ds.ins(val[i]);
};
auto del=[&](int i){
ds.del(val[i]);
for(auto j: adj[i]){
if(j>=l&&j<=r){
ds.del(val[j]);
val[j]^=i+1,val[i]^=j+1;
ds.ins(val[j]);
}
}
};
auto gogo=[&](int l2, int r2){
while(l>l2){
ins(l-1);
l--;
}
while(r<r2){
ins(r+1);
r++;
}
while(l<l2){
l++;
del(l-1);
}
while(r>r2){
r--;
del(r+1);
}
};
for(auto [l2,r2,k,i]: qq){
gogo(l2,r2);
res[i]=ds.kth(k);
}
rep(i,l,r+1) ds.del(val[i]);
rep(q) print(res[i]);
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cout << fixed << setprecision(20);
int t=1;
cin >> t;
while(t--) ahcorz();
}
D1F1 Top-K Tracker (Easy Version) and D1F2 Top-K Tracker (Hard Version)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
int T,n;
vector<int> Sv[N],Sp[N];
void init()
{
cin>>n;
for(int i=1;i<N;i++)
Sv[i].clear(),Sp[i].clear();
}
vector<int> ask(int ty,vector<int> &v)
{
cout<<ty<<" "<<v.size();
for(int i=0;i<v.size();i++)
cout<<" "<<v[i];
cout<<"\n"<<flush;
int k;
if(ty<3) k=min(60,(int)v.size());
else k=min(300,(int)v.size());
vector<int> res;
for(int i=1;i<=k;i++)
{
int t;
cin>>t;
res.push_back(t);
}
return res;
}
void solve()
{
int cnt=0;
vector<int> p(n+4);
for(int i=1;i<=30;i++)
Sv[++cnt].push_back(i);
for(int i=1;i<=30;i++)
{
for(int j=i+1;j<=30;j++)
{
cnt++;
Sv[cnt].push_back(i),Sv[cnt].push_back(j);
}
}
for(int i=1;i<=9;i++)
{
int cur=1;
while(1)
{
int nxt=cur+i;
if(nxt>29) nxt-=29;
cnt++;
Sv[cnt].push_back(30);
Sv[cnt].push_back(cur);
Sv[cnt].push_back(nxt);
cur=nxt;
if(nxt==1) break;
}
}
vector<int> vl(11),vm(11),vr(11);
for(int i=1;i<=10;i++)
vl[i]=i,vm[i]=10+i,vr[i]=20+i;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=10;j++)
{
cnt++;
Sv[cnt].push_back(vl[j]);
Sv[cnt].push_back(vm[j]);
Sv[cnt].push_back(vr[j]);
}
for(int j=0;j<10;j++)
vr[j]=vr[j+1];
vr[10]=vr[0];
}
for(int i=1,cur=1;i<=29;i++)
{
int x=cur,y=cur+1,z=cur+2;
while(x>29) x-=29;
while(y>29) y-=29;
while(z>29) z-=29;
cnt++;
Sv[cnt].push_back(x);
Sv[cnt].push_back(y);
Sv[cnt].push_back(z);
cur+=3;
}
for(int i=1;i<=30;i++)
{
vector<int> v,t;
for(int j=1;j<=n;j++)
if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end())
v.push_back(j);
if(v.empty()) continue;
if(i<30) t=ask(2,v);
else t=ask(4,v);
for(int j=0;j<t.size();j++)
Sp[t[j]].push_back(i);
}
for(int i=1;i<=n;i++)
sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end());
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((!Sp[i].empty())&&Sp[i]==Sv[j]) p[i]=j;
cout<<"! ";
for(int i=1;i<=n;i++)
cout<<p[i]<<(i==n?'\n':' ');
cout<<flush;
}
int main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
}
return 0;
}
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
int T,n;
vector<int> Sv[N],Sp[N],prv[N],prp[N];
void init()
{
srand(time(0));
cin>>n;
for(int i=1;i<N;i++)
Sv[i].clear(),Sp[i].clear(),prv[i].clear(),prp[i].clear();
}
vector<int> ask(int ty,vector<int> &v)
{
cout<<ty<<" "<<v.size();
for(int i=0;i<v.size();i++)
cout<<" "<<v[i];
cout<<"\n"<<flush;
int k;
if(ty<3) k=min(60,(int)v.size());
else k=min(300,(int)v.size());
vector<int> res;
for(int i=1;i<=k;i++)
{
int t;
cin>>t;
res.push_back(t);
}
return res;
}
void solve()
{
int cnt=0,cntr=871,cntpr=30;
vector<int> p(n+4);
for(int i=1;i<=29;i++)
{
cnt++;
Sv[cnt].push_back(i);
cntr--;
Sv[cntr].push_back(i);
}
for(int i=1;i<=29;i++)
{
for(int j=i+1;j<=29;j++)
{
cnt++;
Sv[cnt].push_back(i),Sv[cnt].push_back(j);
cntr--;
Sv[cntr].push_back(i),Sv[cntr].push_back(j);
}
}
for(int i=871,hd=1;i<890;i++,hd+=3)
{
int x=hd,y=hd+1,z=hd+2;
if(x>29) x-=29;
if(y>29) y-=29;
if(z>29) z-=29;
Sv[i].push_back(x),Sv[i].push_back(y),Sv[i].push_back(z);
}
for(int i=1;i<=29;i++)
{
vector<int> v,t;
for(int j=1;j<=n;j++)
if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end())
v.push_back(j);
if(v.empty()) continue;
t=ask(2,v);
for(int j=0;j<t.size();j++)
Sp[t[j]].push_back(i);
}
for(int i=1;i<=n;i++)
sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end());
for(int i=1;i<=n;i++)
{
for(int j=871;j<=n;j++)
if(Sp[i]==Sv[j]) p[i]=j;
}
for(int i=1;i<=n;i++)
{
if(Sp[i].size()==1) prp[Sp[i][0]].push_back(i);
else if(Sp[i].size()==2) prp[30*Sp[i][0]+Sp[i][1]].push_back(i); //hash the set
//|S|>2 and empty set are ignored
}
for(int i=1;i<=n;i++)
{
if(Sv[i].size()==1) prv[Sv[i][0]].push_back(i);
else if(Sv[i].size()==2) prv[30*Sv[i][0]+Sv[i][1]].push_back(i); //hash the set
}
//necessary shuffle
for(int i=1;i<N;i++)
{
if(prp[i].size()<2) continue;
if(rand()&1) swap(prp[i][0],prp[i][1]);
}
for(int i=1;i<=1;i++)
{
vector<int> v,t;
for(int j=1;j<N;j++)
{
if(prp[j].empty()) continue;
else if(prp[j].size()==1)
{
p[prp[j][0]]=prv[j][0];
prp[j].clear();
prv[j].clear();
continue;
}
v.push_back(prp[j][0]);
}
if(v.empty()) continue;
t=ask(3,v);
for(int j=1;j<N;j++)
{
if(prp[j].empty()) continue;
if(t.empty()) break;
if(prv[j][1]==t.back())
{
t.pop_back();
p[prp[j][0]]=prv[j][1];
p[prp[j][1]]=prv[j][0];
}
else
{
p[prp[j][0]]=prv[j][0];
p[prp[j][1]]=prv[j][1];
}
prp[j].clear();
prv[j].clear();
}
}
cout<<"! ";
for(int i=1;i<=n;i++)
cout<<p[i]<<(i==n?'\n':' ');
cout<<flush;
}
int main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
}
return 0;
}
