Help! What's wrong with my code?


#include <bits/stdc++.h>
#define forn( i, n )    for( int i = 0; i < n; i ++ )

using namespace std;

int main() {
   int qq[10000];
   int k, l; double m , n;
   l = 0;
   cin >> k >> n;
   forn( i , n)
     cin >> qq[i];
   forn( i, k+1 ){
     forn( j , n)
       if (qq[j] == i)  l = l+1;
    if ( i != 0 ) {
     m = (l / n * 100);
     l = (int) round(m*100)/100;
     if ( l - m == 0)
       cout << round(m*100)/100 << ".00%" << endl;
     else
       cout << round(m*100)/100 << "%" << endl;
     l = 0;
    }
     }
return 0;
}

//#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;

const int maxn = (int) 1e5 + 10;
int a[maxn], b[maxn];

int main() {
    int n, m;
    cin >> n;
    fo(i, n) cin >> a[i];
    int x, pos, ans;
    cin >> m;
    fo(i, m) {
        cin >> x;
        x = 10000 - x;
        ans = (int)1e9;
        pos = lower_bound(a, a + n, x) - a;
        for (int i = max(0, pos - 1), end = min(n - 1, pos + 1); i <= end; ++i) ans = min(ans, abs(x - a[i]));
        if (!ans) {
            cout << "YES\n";
            re 0;
        }
    }
    cout << "NO\n";
    re 0;
}

#include <stdio.h>

int main(){
    int t=0,n=0,i=0,cont=0;
    int a[65535];
    for(i=0;i<1000;++i){
        a[i]=1;
        t=cont;
        while(cont!=0){
            a[i+cont]=0;
            --cont;
        }
        cont=t;
        i=i+cont;
        ++cont;
    }
    scanf("%d",&n);
    while(n!=0){
        scanf("%d",&t);
        printf("%d\n",a[t-1]);
        --n;
    }
    return(0);
}

using namespace std;
#include<iostream>
#include<stdio.h>
#include<algorithm>
long cnt=0;
long heapsize;
long heapsize1;
void heapsort(struct st a[]);
void buildmaxheap(struct st a[]);
void maxheapify(struct st a[],long index);
long left(long a);
long right(long a);
struct st
{
    long serial;
    long f;
    long l;
};


int main()
{
    long n;
    scanf("%ld",&n);
    long s1;
    long s2;

    struct st* a=new struct st[n+1];
    heapsize=n;
    for(long i=1;i<n+1;i++)
    {
     cnt++;
     a[i].serial=cnt;
     scanf("%ld",&s1);
     getchar();
     scanf("%ld",&s2);
     a[i].f=s1;
     a[i].l=s2;
    }
    heapsort(a);
    for(long i=n;i>0;i--)
    {
        cout<<a[i].f<<" "<<a[i].l<<endl;
    }
}
void heapsort(struct st a[])
{
    buildmaxheap(a);
    for(long i=heapsize;i>=2;i--)
    {
        swap(a[i],a[1]);
        heapsize1--;
        maxheapify(a,1);
    }


}
void buildmaxheap(struct st a[])
{
    heapsize1=heapsize;
   for(long i=heapsize/2;i>=1;i--)
   {
       maxheapify(a,i);
   }
}
void maxheapify(struct st a[],long index)
{
    long l1=left(index);
    long r1=right(index);
    long largest;
    if(l1<=heapsize1&&a[l1].l>=a[index].l)
    {
        if(a[l1].l==a[index].l)
        {
            if(a[l1].serial<a[index].serial)
                largest=l1;
        }
         else
                largest=l1;

    }

    else
        largest=index;
    if(r1<=heapsize1&&a[r1].l>=a[largest].l)
    {
        if(a[r1].l==a[largest].l)
        {
            if(a[r1].serial<a[largest].serial)
                largest=r1;
        }
         else
                largest=r1;

    }
    if(largest!=index)
    {
        swap(a[largest],a[index]);
        maxheapify(a,largest); //maintaining property
    }
}
long left(long a)
{
    return 2*a;
}
long right(long a)
{
    return 2*a+1;
}

Hello,
I'm trying to solve this problem a couple of days. But always get wrong answer 4. I don't know what is the problem may be and this makes me feel badly. Could somebody help me or show the 4th test for me, please?
I can send my code if it's needed.

Please, ban user (id 219673) to make a posts on the forum. Also delete all his posts on the forum if it possible.

Edited by author 20.05.2018 17:29

Had WA 16 because i checked if the plates can fit with > instead of >= (the upper part of the plates can touch.)

Also, if the height of the box is smaller than the plates, and the plates margin fall out of the box, don't forget that their full margins can't touch each other!
Example test:
4 8 1
1 3
1 3
2

Answer: NO

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a,n=0;
        a = in.nextInt();
        a = (int) (Math.pow(1,a)+Math.pow(2,a)+Math.pow(3,a)+Math.pow(4,a));
        int b[] = new int[11000];
        while(a>0){
            if(a%10==0)n++;
            else break;
            a = a/10;
        }
        System.out.print(n);
    }
}

I got ac on this problem using heuristic. Please, add anti-heuristic tests.

Probably dp is possible
Looks like to dp here one should invent something non-trivial because of relatively large n.

Edited by author 04.08.2017 10:43

what is the second test? i have WA on it.

Edited by author 19.05.2018 05:46

Edited by author 19.05.2018 05:46

1) Answer on test 8 is 10^9
2) This may can help you with tests 9, 10:
Pirated is
 Licensed to Pirated
 Pirated to Pirated

Licensed is
 Licensed to Licensed

Cracked is
 Pirated to Pirated
 Licensed to Licensed

Please Add it in tests!

20
10
1 1 even
4 4 even
2 2 odd
5 5 odd
1 3 even
3 5 odd
8 8 even
9 9 even
10 10 even
8 10 even
-1

Correct answer is: 5
My AC prog give 10, but correct answer is 5

I have implemented a stable sort in Rust. I have checked it on task sample array as well as on other sample data that I was generating.

I have implemented simple count sort because of small M. But for some reason it doesn't pass test #3. Any ideas what could be wrong?

```
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for _ in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();
        tuples.push((id, m))
    }

    let tuples = count_sort(&tuples[..]);

    for (id, m) in tuples {
        println!("{} {}", id, m);
    }
}

fn count_sort(input: &[(u32, u8)]) -> Vec<(u32, u8)>  {
    let mut freq = [0 as u8; 101];
    for &(_, m) in input {
        freq[m as usize] += 1;
    }

    let mut output = unsafe { get_empty_vector(input.len()) };

    for i in (1..freq.len()).rev() {
        freq[i - 1] += freq[i];
    }

    for &(id, m) in input.iter().rev() {
        let new_freq = freq[m as usize] - 1;
        freq[m as usize] = new_freq;
        output[new_freq as usize] = (id, m);
    }

    output
}

unsafe fn get_empty_vector<T>(size: usize) -> Vec<T> {
    let mut vec = Vec::with_capacity(size);
    let ptr = vec.as_mut_ptr();
    std::mem::forget(vec);
    let result = Vec::from_raw_parts(ptr, size, size);
    result
}

```

Give the second test, please...

//#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;

vi v = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161};

int main() {
    int n, x;
    cin >> n;
    fo(i, n) {
        cin >> x;
        cout << v[x - 1] << '\n';
    }
}

//#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, k;
    cin >> n >> k;
    cout << max(0, max(n - k - 2, k - 3)) << endl;
}

//#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;

const int maxn = (int) 1e5;
int a[maxn];

int main() {
    int n;
    scanf("%d", &n);
    fo(i, n) scanf("%d", a + i);
    int p1, p2;
    scanf("%d%d", &p1, &p2);
    --p1, --p2;
    if (p1 == p2) {
        int sum1 = 0, sum2 = 0;
        fo(i, p1) sum1 += a[i];
        for (int j = p1 + 1; j < n; ++j) sum2 += a[j];
        cout << max(sum1, sum2) + a[p1] << ' '<< min(sum1, sum2) << endl;
        re 0;
    }
    bool _swap = p1 > p2;
    if (p1 > p2) swap(p1, p2);
    int middle = p1 + (p2 - p1 - 1) / 2 + (((p2 - p1 - 1) & 1) && !_swap);
    ll sum1 = 0, sum2 = 0;
    fo(i, n) {
        if (i <= middle) sum1 += a[i];
        else sum2 += a[i];
    }
    if (_swap) swap(sum1, sum2);
    cout << sum1 << ' '<< sum2 << endl;
}

//#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;

string str1, str2;

int main() {
    cin >> str1 >> str2;
    reverse(all(str1));
    reverse(all(str2));
    int ans = 0;
    while (!str1.empty() || !str2.empty()) {
        if (!str1.empty() && !str2.empty()) {
            char b1 = str1.back();
            char b2 = str2.back();
            if (b1 == b2 && b2 == 'L') str1.erase(str1.size() - 1, 1), str2.erase(str2.size() - 1, 1);
            else if (b1 == 'L') str2.erase(str2.size() - 1, 1);
            else if (b2 == 'L') str1.erase(str1.size() - 1, 1);
            else str1.erase(str1.size() - 1, 1), str2.erase(str2.size() -1, 1);
        } else if (str1.empty()) str2.erase(str2.size() - 1, 1);
        else str1.erase(str1.size() - 1, 1);
        ++ans;
        //cout << str1 << ' ' <<str2 << ' ' << ans << endl;
    }
    cout << ans << endl;
}