solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
if(n%2) cout<<"1\n";
else cout<<"2\n";
}
}
Idea:Davy_D._Kaosar
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
if(n%2) cout<<"0\n";
else{
ll cnt=0;
while(n%2==0){
n/=2;
cnt++;
}
cout<<(cnt/2)<<"\n";
}
}
}
solution
code(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
vector<ll> a(n);
for(ll i=0;i<n;i++) cin>>a[i];
if(n>=5) cout<<"YES\n";
else{
bool ok=true;
for(ll i=0;i<n;i++){
if(a[i]%2!=(i+1)%2) ok=false;
}
if(ok) cout<<"YES\n";
else cout<<"NO\n";
}
}
}
Idea:wuhudsm
solution
code
#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>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int a[N],BIT[N],op1[N],op2[N],d[N];
void add(int p,int x)
{
for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=x;
}
int getsum(int p)
{
int sum=0;
for(int i=p;i;i-=(i&-i)) sum+=BIT[i];
return sum;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) BIT[i]=0;
for(int i=1;i<=n;i++)
{
op1[i]=getsum(a[i]-1);
op2[i]=getsum(n)-getsum(a[i]);
d[i]=op1[i]-op2[i];
add(a[i],1);
}
ll cur=0;
for(int i=1;i<=n;i++) cur+=op2[i];
printf("%I64d ",cur);
sort(d+1,d+n+1);
for(int i=1;i<=n;i++)
{
cur+=d[i];
printf("%I64d%c",cur,i==n?'\n':' ');
}
}
return 0;
}
Idea:xksark (easy version), wuhudsm (hard version)
solution
code(easy version)
~~~~~
~~~~~
code(hard version)
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int N = 2000;
int n, ans[N];
vector<int> f; // position of already found nums
int ask(vector<int> &v) { // asking funciton for case 1
cout << "? " << (int)v.size() + (int)f.size();
for(int &x : f) cout << ' ' << x-1;
for(int &x : v) cout << ' ' << x-1;
cout << endl;
int mex;
cin >> mex;
return mex;
}
int ask(vector<int> &v, vector<int> &u) { // asking function for case 2
cout << "? " << (int)v.size() + (int)u.size() + (int)f.size();
for(int &x : f) cout << ' ' << x-1;
for(int &x : v) cout << ' ' << x-1;
for(int &x : u) cout << ' ' << x-1;
cout << endl;
int mex;
cin >> mex;
return mex;
}
void answer(int i,int v)
{
cout<<"! "<<i<<' '<<v<<endl;
cout<<flush;
}
void rand_shuffle(vector<int> &v, vector<int> &q1, vector<int> &q2) {
int sz = v.size();
for(int i = 0; i < sz; ++i) { // random shuffle
int j = rand() % (i + 1);
swap(v[i], v[j]);
}
for(int i = 0; i < sz; ++i) {
if(i + i < sz) {
q1.push_back(v[i]);
} else {
q2.push_back(v[i]);
}
}
}
void solve() {
cin >> n;
set<int> pos;
for(int i = 1; i <= n; ++i) pos.insert(i);
for(int cur = 1; cur < n; cur += 2) {
vector<int> A(all(pos)), B(all(pos));
while(A.size() > 1 || B.size() > 1) {
bool ok = (A[0] == B[0]); // To check for case 1 or 2
vector<int> q1, q2, q3, q4;
rand_shuffle(A, q1, q2); // shuffle and split the set S0
if(ok) { // Case 1 : S0 == S1
int mex = ask(q1);
if(mex > cur) {
A = q1;
B = q1;
} else if(mex == cur) {
A = q1;
B = q2;
} else {
mex = ask(q2);
if(mex > cur) {
A = q2;
B = q2;
} else {
A = q2;
B = q1;
}
}
} else { // Case 2 : S0 != S1
rand_shuffle(B, q3, q4); // shuffle and split the set S1
int mex = ask(q1, q3);
if(mex > cur) {
A = q1;
B = q3;
} else if(mex == cur) {
A = q1;
B = q4;
} else {
mex = ask(q2, q3);
if(mex > cur) {
A = q2;
B = q3;
} else {
A = q2;
B = q4;
}
}
}
}
//
answer(A[0]-1,cur-1);
answer(B[0]-1,cur);
//
ans[A[0]] = cur - 1; // fill the answer
ans[B[0]] = cur;
pos.erase(A[0]); // erase the already used positions
pos.erase(B[0]);
f.push_back(A[0]); // add used positions for all future queries
f.push_back(B[0]);
}
if(n & 1) {
answer(*pos.begin()-1,n-1);
ans[*pos.begin()] = n - 1;
}
/*
cout << "!";
for(int i = 1; i <= n; ++i) cout << ' ' << ans[i];
cout << endl;
*/
f.clear();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
srand(chrono::steady_clock::now().time_since_epoch().count());
int tt = 1;
cin >> tt;
while(tt--) {
solve();
}
}
Idea:wuhudsm
solution
code(C++)
#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>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int a[N],b[N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int NIM_SUM=0,cur=0;
vector<int> v;
map<int,int> cnt;
v.push_back(0);
for(int i=1;i<=n;i++)
{
if(!cnt[a[i]]) v.push_back(a[i]);
cnt[a[i]]++;
}
sort(v.begin(),v.end());
for(int i=v.size()-1;i;i--)
{
cur+=cnt[v[i]];
if((v[i]-v[i-1])&1) NIM_SUM^=cur;
}
printf("%s\n",NIM_SUM?"YES":"NO");
}
return 0;
}
