# include <bits/stdc++.h> using namespace std; using ll = long long; #define vec vector #define int long long #define ld long double #define f first #define s second #define pb push_back #define fe(x, a) for (auto& x : a) #define pw(x) (1ll << x) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using pii = pair<int, int>; const int mod = 1e9 + 7; const ll OO = 1e16; const int N = 1e5 + 2; const ld eps = 1e-3; template<typename T> bool umn(T &a, T b) { return a > b ? (a = b, 1) : 0; } template<typename T> bool umx(T &a, T b) { return a < b ? (a = b, 1) : 0; } void solve() { int n, best = -1, ans = 0; cin >> n; set<pii> setik; for (int i = 0, x; i < n + 1; ++i) { x = -OO; if (i < n) cin >> x; if (i && x < (*setik.begin()).f) if (umx(best, i - (*setik.begin()).s - !(*setik.begin()).s)) ans = (*setik.begin()).s; setik.insert({x, i}); } cout << ans + 1; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); } What is test 11? Edited by author 05.12.2021 02:11 5 5 4 3 2 1 (2) 1 1 (1) 10 3 3 4 2 5 6 1 9 9 3 (4) wrong answer on 1st test obmanul suka whats in test 8 ? cant find out :( try to use this one 5 2 3 0 4 5 Hint: when the pirate becomes the current best option, he is also being compared. Thus in the test case above pirate 1 will be compared 2 times, while pirate 3 will be compared 3! GL!!! Try this test 6 2 2 2 1 1 1 ans: 4 //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; int main() { int n, x; ii ans = mp(-1, 0); pair <ii, int> cur; cin >> n >> cur.fi.fi; cur.fi.se = cur.se = 0; fo(i, n - 1) { cin >> x; if (x >= cur.fi.fi) ++cur.fi.se; else { cur.fi.se++; ans = max(ans, mp(cur.fi.se, cur.se)); cur = mp(mp(x, 1), i + 1); } } ans = max(ans, mp(cur.fi.se, cur.se)); cout << ans.se + 1 << endl; } What's the meaning of the question ? I tried to get it but in vain, even the test unclear for me I'll explain the test. 6 2 5 3 4 1 9 The first one is chosen as current candidate, and has 2 disadvantages. Then, he is compared with 2nd pirate (5 disadvantages), 3rd (3), 4th (4), 5th (1). When comparing with 5th pirate, we see that he has less disadvantages (1) than current candidate (2). So he becomes the current candidate. And then we finally compare him with last pirate (9 disadvantages). In the end, 1st pirate with 2 disadvantages was compared to 2nd, 3rd, 4th, 5th — compared 4 times; 2nd pirate with 5 disadvantages was compared to 1st — compared 1 times; 3rd pirate with 3 disadvantages was compared to 1st — compared 1 times; 4th pirate with 4 disadvantages was compared to 1st — compared 1 times; 5th pirate with 1 disadvantages was compared to 1st, 6th — compared 2 times; 6th pirate with 9 disadvantages was compared to 5th — compared 1 times; Out of all the pirates, the 1st one has the most compare times — 4. Thus, we output 1 — the index of a pirate who was compared most times. But, if several pirates were compared the same amount of times — say, if 5th one was also compared 4 times (if there were 2 more pirates in input) — then both answers "1" or "4" would be correct in this case. Is this any clearer? for WA#8 check this test 12 9 10 6 7 8 3 4 5 2 4 4 4 answer is 3 They should be pairwise different. Whatever, this test help me. even no idea tried this 10 3 5 6 7 2 8 9 7 5 6 5 get 5 My error was that I didn't check after the end of the loop if my current numbers of swaps is bigger than the now kept max . Try this test : 8 2 3 4 1 5 6 7 8 Answer : 4 check this test: 7 2 3 4 1 5 6 7 Answer : 4 program ytr; var n,i,p,d,t,min:longint; a:array[1..100000] of longint; b:boolean; begin readln(n); t:=-1; b:=true; p:=1; for i:=1 to n do begin read(a[i]); if b then begin min:=a[i]; b:=false; end; inc(t); if a[i]<min then begin p:=i-t; d:=t; t:=0; min:=a[i]; end; if (i=n) and (t>d) then p:=i-t; end; write(p); end. Can anyone provide a sample for test 3? Thanks. 1 1 Your result should be 1 but I think your program will output 0 That was the problem in my case WA#8 #include<iostream>; using namespace std; int main() { int a[100002],i,n,record,maxrecord,irecord,imax,nmax; cin >> n; cin >>a[1]; imax=1; nmax=a[1]; record=1; irecord=1; maxrecord=1; for(i=2;i<=n;i++) { cin >> a[i]; if (a[i]>nmax) { ++record; if (maxrecord<record) { maxrecord=record; irecord=imax; } } else { imax=i; nmax=a[i]; record=1; } } cout << irecord; system ("PAUSE"); return 0; } what is test 8. i get wrong answew :( :( Edited by author 10.11.2012 16:31 Try something like: 5 5 4 3 2 1 The answer should be anything except 1 or 5. The first pirate is compared and switched straight away. This is also the first comparison for the 2nd pirate, which is compared with 3rd before before swapping. I can't understand what's wrong? #include <iostream> using namespace std; int main() { int n,s=1,max,j,i; cin>>n; int *a=new int[n]; for(i=0; i<n;i++) cin>>a[i]; s=1;max=0; for(i=0;i<n;i++) { j=i+1; while(a[i]<a[j]) j++; if (j-i>=s) { if (max>0) s=j-i+1; else s=j-i; max=i; } }; cout<<max+1;
delete a; return 0; } Edited by author 07.02.2013 01:30 Who know test#8? Edited by author 10.11.2012 15:27 Same "trash", bro. Remember when the pirate is exchanged, this is also counted as a comparison for the new pirate |
|