QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#93695 | #5521. Excellent XOR Problem | CUET_infinite_tsukuyomi# | WA | 23ms | 4684kb | C++17 | 3.4kb | 2023-04-02 04:45:53 | 2023-04-02 04:45:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long int li;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
//typedef long long int;
#define endl "\n"
#define f(i,a,b) for(int i=a;i<=(b);i++)
#define r(i,a,b) for(int i=a;i>=(b);i--)
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define mid(s,l) (s+(l-s)/2)
#define umap unordered_map
#define pb push_back
#define mp make_pair
//#define int long long
//const int INF = int(1e9);
//const int MOD = int(1e9) + 7;
//const ld EPS = 1e-18;
//const ld PI = acos(-1.0);
void GG()
{
int n;
cin >> n;
vector<int> v(n + 1);
vector<int> pref(n + 1);
int fnz = -1;
for(int i = 1; i <= n; i++){
cin >> v[i];
if(v[i] > 0 && fnz == -1) fnz = i;
pref[i] = pref[i - 1] ^ v[i];
}
if(n == 2){
if(v[1] == v[2]) cout << "NO" << endl;
else{
cout << "YES" << endl;
cout << 2 << endl;
cout << 1 << ' ' << 1 << endl;
cout << 2 << ' ' << 2 << endl;
}
return;
}
else{
int ls = v[1];
int rs = v[n];
int ms = pref[n - 1] ^ pref[1];
if(ls != ms && ls != rs && ms != rs){
cout << "YES" << endl;
cout << 3 << endl;
cout << 1 << ' ' << 1 << endl;
cout << 2 << ' ' << n - 1 << endl;
cout << n << ' ' << n << endl;
return;
}
else if(ls == ms && ms == rs && rs == 0){
if(fnz == -1) {cout << "NO" << endl; return;}
else{
ls = pref[fnz];
//cout << fnz << endl;
for(int i = n - 1; i > fnz + 1; i--){
int val = pref[n - 1] ^ pref[i - 1];
//cout << i << ' ' << fnz << ' ' << val << endl;
if(val != 0 && val != ls){
cout << "YES" << endl;
cout << 3 << endl;
cout << 1 << ' ' << fnz << endl;
cout << fnz + 1 << ' ' << i - 1 << endl;
cout << i << ' ' << n << endl;
return;
}
}
}
cout << "NO" << endl;
return;
}
else if(ls == ms && rs == 0){
for(int i = n - 1; i > 2; i--){
int val = pref[n - 1] ^ pref[i - 1];
if(val != 0 && val != ls){
cout << "YES" << endl;
cout << 3 << endl;
cout << 1 << ' ' << 1 << endl;
cout << 2 << ' ' << i - 1 << endl;
cout << i << ' ' << n << endl;
return;
}
}
cout << "NO" << endl;
return;
}
else if(ls == rs && ms == 0){
for(int i = 2; i < n - 1; i++){
int val = pref[i] ^ pref[1];
if(val != 0 && val != ls){
cout << "YES" << endl;
cout << 3 << endl;
cout << 1 << ' ' << i << endl;
cout << i + 1 << ' ' << n - 1 << endl;
cout << n << ' ' << n << endl;
return;
}
}
cout << "NO" << endl;
return;
}
else if(ms == rs && ls == 0){
for(int i = 2; i < n - 1; i++){
int val = pref[i] ^ pref[1];
if(val != 0 && val != ls){
cout << "YES" << endl;
cout << 3 << endl;
cout << 1 << ' ' << i << endl;
cout << i + 1 << ' ' << n - 1 << endl;
cout << n << ' ' << n << endl;
return;
}
}
cout << "NO" << endl;
return;
}
else{
cout << "YES" << endl;
cout << 2 << endl;
cout << 1 << ' ' << n - 1 << endl;
cout << n << ' ' << n << endl;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ttc=1;
cin>>ttc;
//int cnt=0;
while(ttc--)
{
//cout<<"Case "<<++cnt<<": ";
GG();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3412kb
input:
4 2 0 0 3 1 2 3 5 16 8 4 2 1 6 42 42 42 42 42 42
output:
NO YES 3 1 1 2 2 3 3 YES 3 1 1 2 4 5 5 NO
result:
ok Correct (4 test cases)
Test #2:
score: 0
Accepted
time: 13ms
memory: 4632kb
input:
1 200000 0 0 104990627 0 104990627 0 0 0 0 104990627 0 104990627 0 0 104990627 104990627 0 0 0 0 0 104990627 0 0 0 104990627 104990627 104990627 0 104990627 0 104990627 104990627 0 104990627 0 0 0 104990627 104990627 0 0 104990627 104990627 0 0 104990627 0 0 0 0 0 104990627 104990627 0 0 0 0 0 10499...
output:
YES 2 1 199999 200000 200000
result:
ok Correct (1 test case)
Test #3:
score: 0
Accepted
time: 18ms
memory: 4576kb
input:
1 200000 916550535 1039111536 183367143 845311658 473404911 844600350 249761080 860927112 268559756 661297994 448456545 184790162 804023458 655065019 442145717 130497524 509071033 644651807 1039510287 766490362 514960668 612238468 863513676 417538457 839195481 901404895 760875212 983171045 343221187...
output:
YES 3 1 1 2 199999 200000 200000
result:
ok Correct (1 test case)
Test #4:
score: 0
Accepted
time: 14ms
memory: 4684kb
input:
1 200000 697100980 63360185 3577101 75632048 903073319 644702701 1017474476 268785811 6091842 227390753 270800416 554896940 318364388 526066510 354510498 1034952286 613138496 176305121 384248064 715019967 999545181 91222841 1063728923 665773338 354670745 473570604 220064105 301115885 1038664738 3094...
output:
YES 3 1 1 2 199999 200000 200000
result:
ok Correct (1 test case)
Test #5:
score: 0
Accepted
time: 19ms
memory: 4556kb
input:
1 200000 446225258 446225258 446225258 446225258 0 0 446225258 446225258 0 446225258 0 0 446225258 0 446225258 0 446225258 446225258 446225258 0 446225258 0 0 446225258 0 0 446225258 446225258 446225258 446225258 0 0 0 446225258 0 446225258 446225258 0 0 0 0 446225258 446225258 446225258 446225258 0...
output:
YES 3 1 139152 139153 199999 200000 200000
result:
ok Correct (1 test case)
Test #6:
score: 0
Accepted
time: 15ms
memory: 4612kb
input:
1 200000 917884074 0 917884074 917884074 0 0 0 917884074 917884074 0 917884074 0 0 0 917884074 0 917884074 917884074 0 917884074 0 917884074 0 917884074 0 917884074 0 0 917884074 0 0 0 0 917884074 0 0 917884074 0 0 917884074 0 0 0 917884074 0 0 917884074 917884074 917884074 0 917884074 917884074 917...
output:
NO
result:
ok Correct (1 test case)
Test #7:
score: 0
Accepted
time: 23ms
memory: 4684kb
input:
1 200000 38752313 357331606 537948798 987818688 44594898 45009755 99389192 639845557 292429925 1073152680 811573855 591475451 1008870823 139070983 91604841 527091101 925340882 918748711 565945042 560608781 305815075 675659609 590632841 336736157 1048580186 263809556 745114432 402434054 977511741 738...
output:
YES 3 1 1 2 199999 200000 200000
result:
ok Correct (1 test case)
Test #8:
score: 0
Accepted
time: 19ms
memory: 4572kb
input:
1 200000 893044581 455322080 358158755 218139078 474263307 918853931 867102588 47704257 29962011 639245440 633917727 961582229 523211753 10072474 3969623 357804040 1029408344 450402025 984424643 509138385 790399588 154643982 790848088 584971038 564055450 909717089 204303325 794120719 599213467 16634...
output:
YES 3 1 1 2 199999 200000 200000
result:
ok Correct (1 test case)
Test #9:
score: -100
Wrong Answer
time: 18ms
memory: 4640kb
input:
1 200000 0 185376886 185376886 0 0 185376886 0 0 0 185376886 185376886 185376886 0 185376886 0 185376886 0 0 0 185376886 0 185376886 0 0 185376886 0 0 185376886 185376886 0 0 0 0 185376886 185376886 185376886 185376886 0 185376886 185376886 185376886 0 185376886 185376886 185376886 0 185376886 18537...
output:
YES 3 1 2 3 199999 200000 200000
result:
FAIL all xors must be different (test case 1)