Submission #27547262

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

bool cust(pair<ll,ll>&x,pair<ll,ll>&y){
    if(x.first!=y.first)return x.first<y.first;
    else return x.second>y.second;
}
ll power(long long x, ll y, ll p)
{
    ll res = 1;     
    x = x % p; 
    if (x == 0) return 0; 
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1; 
        x = (x*x) % p;
    }
    return res;
}
ll cal(int &n,ll &x1,ll &y1,vector<pair<ll,ll>>&x,vector<pair<ll,ll>>&y){
	    ll last=0;
	    for(int i=0;i<n;i++){
	        if(x1==x[i].first||x1==y[i].first){
	            if(y1>=x[i].second&&y1<=y[i].second)continue;
	            else last+=min(abs(y[i].second-y1),abs(x[i].second-y1));
	        }
	        else if(y1==x[i].second||y1==y[i].second){
	            if(x1>=x[i].first&&x1<=y[i].first)continue;
	            else last+=min(abs(x[i].first-x1),abs(x[i].first-x1));
	        }
	        else{
	            ll z=1e18;
	            z=min(abs(x[i].first-x1)+abs(x[i].second-y1),min(abs(x[i].first-x1)+abs(y[i].second-y1),min(abs(y[i].first-x1)+abs(y[i].second-y1),abs(y[i].first-x1)+abs(x[i].second-y1))));
	            last+=z;
	        }
	    }
	    return last;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1,l;
    //cin>>t;
    ll mod=998244353;
	for(int q=1;q<=t;q++) {
	    int n;
	    cin>>n;
	    vector<pair<ll,pair<ll,ll>>>arr;
	    for(int i=1;i<=n;i++){
	        ll x;
	        cin>>x;
	        arr.push_back({x,{0,i}});
	    }
	    ll rs=0;
	    for(int i=1;i<=n;i++){
	        ll x;
	        cin>>x;
	        rs+=x;
	        if(i<n)
	        arr.push_back({x,{i,i+1}});
	        else arr.push_back({x,{i,1}});
	    }
	    sort(arr.begin(),arr.end());
	    vector<int>v(n+1,0);
	    ll ans=0;
	    int f=0;
	    for(int i=0;i<2*n;i++){
	        if(arr[i].second.first==0){
	            int l=arr[i].second.second;
	            if(v[l]==0){
	                if(l!=1&&l!=n){
	                    if(v[l-1]==0&&v[l+1]==0){
	                        v[l]=1;ans+=arr[i].first;
	                        f=1;
	                    }
	                }
	                else if(l==1){
	                    if(v[l+1]==0&&v[n]==0){
	                        v[l]=1;
	                        ans+=arr[i].first;
	                        f=1;
	                    }
	                }
	                else {
	                    if(v[l-1]==0&&v[1]==0){
	                        v[l]=1;
	                        ans+=arr[i].first;
	                        f=1;
	                    }
	                }
	            }
	        }
	        else if(arr[i].second.second==0){
	            int l=arr[i].second.first;
	            if(v[l]==0){
	                if(l!=1&&l!=n){
	                    if(v[l-1]==0&&v[l+1]==0){
	                        v[l]=1;ans+=arr[i].first;
	                        f=1;
	                    }
	                }
	                else if(l==1){
	                    if(v[l+1]==0&&v[n]==0){
	                        v[l]=1;
	                        ans+=arr[i].first;
	                        f=1;
	                    }
	                }
	                else {
	                    if(v[l-1]==0&&v[1]==0){
	                        v[l]=1;
	                        ans+=arr[i].first;
	                        f=1;
	                    }
	                }
	            }
	        }
	        else if(v[arr[i].second.first]==0&&v[arr[i].second.second]==0){
	            ans+=arr[i].first;
	            //cout<<arr[i].first<<" "<<arr[i].second.first<<" "<<arr[i].second.second<<endl;
	            
	        }
	        //cout<<arr[i].first<<" "<<arr[i].second.first<<" "<<arr[i].second.second<<endl;
	    }
	    if(f==1)cout<<min(ans,rs);
	    else cout<<rs<<endl;
	}
}

Submission Info

Submission Time
Task F - Make Bipartite
User prateek3110
Language C++ (GCC 9.2.1)
Score 0
Code Size 3961 Byte
Status WA
Exec Time 92 ms
Memory 15500 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:13: warning: unused variable ‘l’ [-Wunused-variable]
   49 |     int t=1,l;
      |             ^
./Main.cpp:51:8: warning: unused variable ‘mod’ [-Wunused-variable]
   51 |     ll mod=998244353;
      |        ^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 16
WA × 20
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 6 ms 3508 KiB
001.txt AC 4 ms 3628 KiB
002.txt AC 55 ms 15428 KiB
003.txt AC 2 ms 3556 KiB
004.txt AC 6 ms 3620 KiB
005.txt AC 75 ms 15424 KiB
006.txt AC 2 ms 3564 KiB
007.txt AC 3 ms 3572 KiB
008.txt AC 2 ms 3576 KiB
009.txt AC 2 ms 3504 KiB
010.txt AC 70 ms 15356 KiB
011.txt AC 61 ms 15500 KiB
012.txt AC 65 ms 15412 KiB
013.txt AC 58 ms 15376 KiB
014.txt WA 56 ms 9320 KiB
015.txt WA 84 ms 15424 KiB
016.txt WA 43 ms 9396 KiB
017.txt WA 25 ms 6252 KiB
018.txt WA 40 ms 9416 KiB
019.txt WA 23 ms 6328 KiB
020.txt WA 11 ms 4104 KiB
021.txt WA 31 ms 6264 KiB
022.txt WA 66 ms 15436 KiB
023.txt WA 73 ms 15420 KiB
024.txt WA 85 ms 15356 KiB
025.txt WA 84 ms 15436 KiB
026.txt WA 83 ms 15424 KiB
027.txt WA 90 ms 15428 KiB
028.txt WA 90 ms 15424 KiB
029.txt WA 90 ms 15348 KiB
030.txt WA 92 ms 15356 KiB
031.txt WA 92 ms 15420 KiB
032.txt WA 90 ms 15436 KiB
033.txt WA 92 ms 15428 KiB
example0.txt AC 2 ms 3560 KiB
example1.txt AC 3 ms 3580 KiB